题目描述
给定一个长度为 $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]$ 内所有连续子区间的最大前缀和之和。