题目描述
给定一个长度为 $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)$ 在线回答询问。
代码
离线 / 莫队
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 |
#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; } |
在线
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 |
#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]$ 内所有连续子区间的最大前缀和之和。
莫队转移的思路很优秀啊…