【HNOI 2016】序列 / 题解

【HNOI 2016】序列 / 题解

题目描述

给定一个长度为 $n$ 的序列 $a$,每次询问 $[l,r]$ 内所有连续子区间的区间最小值。

思路

我们分别讲解如何使用离线 / 在线算法解决本题。

离线 / 莫队

使用莫队将问题离线后,我们需要思考如何从 $[l,r-1]$ 的答案推至 $[l,r]$ 的答案。

首先,我们知道一共新增了 $r-l+1$ 个,以 $r$ 为右端点的区间。如果将 $[l,r]$ 中区间最小值的位置记为 $p$,这些区间可以根据是否包含 $p$ 划分为两部分:对于包含 $p$ 的那 $p-l+1$ 个区间,显然它们对答案的贡献都等于 $a[p]$。

对于剩下的 $r-p$ 的区间,我们不妨设一个辅助数组 $f$ 来帮助我们求解。

设 $f[l][r]$ 表示右端点为 $r$,左端点为 $[l,r]$ 中一点的所有区间的答案。和上面的思路一样,我们记 $r$ 之前第一个小于 $a[r]$ 的位置为 $pre$,那么很容易得到这个式子:

$$f[l][r]=f[l][pre]+a[r]\times (r-pre)$$

因此,新增的右端点 $r$ 对答案的贡献为

$$a[p]\times(p-l+1)+f[p+1][r] $$

考虑到 $p \leq pre$,我们可以直接把式子写成

$$a[p] \times(p-l+1)+f[p+1][pre] + a[r]\times(r-pre)$$

我们发现,$f$ 数组的第一维 $l$ 在式子中并没有起到作用,所以我们可以忽略这一维,把 $f$ 写成关于 $l$ 的前缀形式,也就是我们定义新的 $f’$,使得

$\begin{aligned}f'[r]=&\sum_{l=1}^r f[l][r] \ =&f'[pre]+a[r]\times(r-pre)\end{aligned}$

预处理出 $f’$,我们就可以 $\Theta(1)$ 计算 $r$ 对答案的贡献

$a[p] \times(p-l+1)+f[r] – f[p]$

对称地处理 $l$ 对答案的贡献即可。

在线

离线算法给了我们很多启发。

我们预处理出了贼好用的 $f’$ 数组,用来表示固定右端点时,所有区间的答案和;也预处理出了固定左端点时对应的数组。那么我们前缀和一下是不是就能在线回答询问了?我们还是小心地推一下式子。

对于区间 $[l,r]$,我们还是记最小值的出现位置为 $p$。对于跨越 $p$ 的区间,它们对答案的贡献为 $a[p]\times(r-p+1)\times(p-l+1)$。

现在我们考虑区间 $[p+1,r]$ 的答案。由离线做法我们知道,$x$ 为右端点时对答案的贡献为 $f'[x]-f'[p]$。那么我们将 $(r-p)$ 个右端点的答案累加起来,就等于 $f'[p+1]-f'[p]+f'[p+2]-f'[p]+ \cdots f'[r]-f'[p]$。

我们记 $g$ 为 $f’$ 的前缀和,那么上面这个式子就等于 $g[r]-g[p]-f'[p]\times(r-p)$。对于区间 $[l,p-1]$,对称地处理即可。

也就是说,求出 $p$ 之后,我们可以 $\Theta(1)$ 在线回答询问。

代码

离线 / 莫队

#include <bits/stdc++.h>
#define ll long long
#define maxn 1000001
using namespace std;

int read(){
    int x=0,flag=1;char ch=getchar();
    while(!isdigit(ch)&&ch!='-') ch=getchar();
    if (ch=='-') flag=-1,ch=getchar();
    while(isdigit(ch)) x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    return x*flag;
}

int n,a[maxn],q,len;
int p[20][maxn];
int pre[maxn],suf[maxn];
ll f_l[maxn],f_r[maxn];
ll ans[maxn],cur;

void init(){
    for (int i=1;i<=n;++i)
        p[0][i]=i;
    for (int j=1;j<=19;++j)
        for (int i=1;i<=n;++i)
            if (i+(1<<j)-1<=n)
                p[j][i]=(a[p[j-1][i]]<a[p[j-1][i+(1<<(j-1))]])?
                p[j-1][i]:p[j-1][i+(1<<(j-1))];

    int s[maxn],top=0;
    for (int i=1;i<=n;++i){
        while(top&&a[s[top]]>a[i])
        suf[s[top--]]=i;
        pre[i]=s[top],s[++top]=i;
    }
    while(top)
        pre[s[top]]=s[top-1],
        suf[s[top--]]=n+1;

    for (int i=1;i<=n;++i)
    f_r[i]=f_r[pre[i]]+1ll*a[i]*(i-pre[i]);
    for (int i=n;i>=1;--i)
    f_l[i]=f_l[suf[i]]+1ll*a[i]*(suf[i]-i);
}

struct Ask{
    int l,r,id;
    Ask(int a=0,int b=0,int c=0){
        l=a,r=b,id=c;
    }
    bool operator < (const Ask &x) const{
        return l/len==x.l/len?r<x.r:l/len<x.l/len;
    }
}T_T[maxn];

int Query(int l,int r){
    int k=log(r-l+1.0)/log(2.0);
    return (a[p[k][l]]<a[p[k][r-(1<<k)+1]])?
        p[k][l]:p[k][r-(1<<k)+1];
}

ll Left(int L,int R){
    int pos=Query(L,R);
    return 1ll*a[pos]*(R-pos+1)+f_l[L]-f_l[pos];
}

ll Right(int L,int R){
    int pos=Query(L,R);
    return 1ll*a[pos]*(pos-L+1)+f_r[R]-f_r[pos];
}

int main(){
    n=read(),q=read();
    len=sqrt(n);
    for (int i=1;i<=n;++i)
        a[i]=read();
    a[0]=a[n+1]=INT_MAX;
    init();
    for (int i=1;i<=q;++i){
        int l=read(),r=read();
        T_T[i]=Ask(l,r,i);
    }
    sort(T_T+1,T_T+1+q);
    int l=T_T[1].l,r=l-1;
    for (int i=1;i<=q;++i){
        int L=T_T[i].l,R=T_T[i].r;
        while(l>L) cur+=Left(l-1,r),l--;
        while(r<R) cur+=Right(l,r+1),r++;
        while(l<L) cur-=Left(l,r),l++;
        while(r>R) cur-=Right(l,r),r--;
        ans[T_T[i].id]=cur;
    }
    for (int i=1;i<=q;++i)
        printf("%lld\n",ans[i]);
    return 0;
}

在线

#include <bits/stdc++.h>
#define ll long long
#define maxn 100010
using namespace std;

int read(){
    int x=0,flag=1;char ch=getchar();
    while(!isdigit(ch)&&ch!='-') ch=getchar();
    if (ch=='-') flag=-1,ch=getchar();
    while(isdigit(ch)) x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
    return x*flag;
}

int n,a[maxn],q,len;
int p[20][maxn];
int pre[maxn],suf[maxn];
ll f_l[maxn],f_r[maxn];
ll g_l[maxn],g_r[maxn]; 
ll ans[maxn],cur;

void init(){
    for (register int i=1;i<=n;++i)
        p[0][i]=i;
    for (register int j=1;j<=19;++j)
        for (register int i=1;i<=n;++i)
            if (i+(1<<j)-1<=n)
                p[j][i]=(a[p[j-1][i]]<a[p[j-1][i+(1<<(j-1))]])?
                p[j-1][i]:p[j-1][i+(1<<(j-1))];
            else break;

    int s[maxn],top=0;
    for (register int i=1;i<=n;++i){
        while(top&&a[s[top]]>a[i])
        suf[s[top--]]=i;
        pre[i]=s[top],s[++top]=i;
    }
    while(top)
        pre[s[top]]=s[top-1],
        suf[s[top--]]=n+1;

    for (register int i=1;i<=n;++i)
    f_r[i]=f_r[pre[i]]+1ll*a[i]*(i-pre[i]),
    g_r[i]=g_r[i-1]+f_r[i];
    for (register int i=n;i>=1;--i)
    f_l[i]=f_l[suf[i]]+1ll*a[i]*(suf[i]-i),
    g_l[i]=g_l[i+1]+f_l[i];
}

inline int Query(int l,int r){
    int k=log(r-l+1.0)/log(2.0);
    return (a[p[k][l]]<a[p[k][r-(1<<k)+1]])?
        p[k][l]:p[k][r-(1<<k)+1];
}

void print(ll x){
    if (!x) return;
    print(x/10);
    putchar('0'+x%10);
}

ll solve(int l,int r){
    int p=Query(l,r);
    ll res=1ll*a[p]*(r-p+1)*(p-l+1);
    res+=g_r[r]-g_r[p]-f_r[p]*(r-p);
    res+=g_l[l]-g_l[p]-f_l[p]*(p-l);
    return res;
}

int main(){
    n=read(),q=read();
    len=sqrt(n);
    for (register int i=1;i<=n;++i)
        a[i]=read();
    a[0]=a[n+1]=INT_MAX;
    init();
    for (register int i=1;i<=q;++i){
        int l=read(),r=read();
        printf("%lld\n",solve(l,r));
    }
    return 0;
}

附加例题

记长度为 $n$ 的序列 $A$ 的最大前缀和为 $\forall j \in [1,n],\sum_{i=1}^j A_i$ 的最大值。

给定长度为 $n$ 的序列 $a$,每次询问区间 $[l,r]$ 内所有连续子区间的最大前缀和之和。