HNOI2016 序列 题解
我做离线版本时往了偏序方向想，但是发现非常麻烦。直到看到了在线版本的容斥做法，发现既好写又跑得快。
首先考虑容斥，我们不妨把一个询问 \([L,R]\) 中最小值的位置 \(pos\) 求出来。
- 子区间跨过 \(pos\)，贡献即 \((pos-L+1)\times(R-pos+1)\times a_{pos}\)。
- 子区间在 \(pos\) 左侧。
- 子区间在 \(pos\) 右侧。
对于子区间在 \(pos\) 左侧和右侧是等价的，我们讨论在左侧的情况，可以考虑容斥，经过尝试可以发现一下的构造方式是可行的。
以下我们记 \([l,r][L,R]\) 表示左端点在 \([l,r]\)，右端点在 \([L,R]\) 的所有区间最小值的和。
那么
\[[L,pos-1][L,pos-1]=[L,n][L,n]-[pos,n][pos,n]-[L,pos-1][pos,n] \]在这里我们运用了 \([L,pos-1][pos,n]\) 一定跨过 \(pos\) 的性质来求。我们看具体怎么做。
设 \(f_i=[i,n][i,n]\)。可以递推求 \(f_i\)，有 \(f_i=f_{i+1}+[i,i][i,n]\)。
怎么求 \([i,i][i,n]\)，考虑还可以递推，设 \(F_i=[i,i][i,n]\)。
考虑把最小值为 \(a_i\) 的区间一并贡献，那么设 \(r_i\) 表示 \(i\) 右侧第一个比 \(a_i\) 小的位置，对于 \(r_i\) 及其右侧的贡献就是 \(F_{r_i}\)，所以就有
\[F_i=(r_i-i)\times a_i+F_{r_i} \]\(r_i\) 可以从右往左扫一遍用单调栈求。
我们再来看 \([L,pos-1][pos,n]\)，前面说了要运用它跨过 \(pos\) 的性质，由于 \(pos\) 是 \([L,R]\) 内最小的位置，所以 \([L,pos-1]\) 都不大于 \(pos\)，于是就有等价
\[[L,pos-1][pos,n]=(pos-L)\times[pos][pos,n]=(pos-L)\times F_{pos} \]那么这道题就做完了，瓶颈在于 RMQ，可以使用 ST 表做到 \(O(n\log n+Q)\)，或者使用 \(O(n)\sim O(1)\) RMQ 做到 \(O(n+Q)\)。
代码难度较低，细节不多。
AC 代码：
using gen::init;
using gen::input;
using gen::output;
using gen::finish;
const int N=1e5+5;
int a[N];
pair<int,int> mn[17][N];
int get(int l,int r){
int len=r-l+1;
return min(mn[__lg(len)][l],mn[__lg(len)][r-(1<<__lg(len))+1]).second;
}
int stk[N],top=0;
int L[N],R[N];
ll f[N],F[N],g[N],G[N];
signed main(){
read(n,Q,type);
fo(i,1,n){
read(a[i]);
mn[0][i]={a[i],i};
while(top&&a[stk[top]]>=a[i])--top;
L[i]=stk[top];
stk[++top]=i;
F[i]=F[L[i]]+(ll)(i-L[i])*a[i];
f[i]=f[i-1]+F[i];
}
stk[top=0]=n+1;
fd(i,n,1){
while(top&&a[stk[top]]>=a[i])--top;
R[i]=stk[top];
stk[++top]=i;
G[i]=G[R[i]]+(ll)(R[i]-i)*a[i];
g[i]=g[i+1]+G[i];
}
fo(i,1,__lg(n)){
fo(j,1,n-(1<<i)+1){
mn[i][j]=min(mn[i-1][j],mn[i-1][j+(1<<i-1)]);
}
}
if(type==1)init();
while(Q--){
int l,r;
if(type==1)input(l,r);
else read(l,r);
ull ans=0;
int pos=get(l,r);
ans=(ull)a[pos]*(pos-l+1)*(r-pos+1);
ans+=g[l]-g[pos]-(ll)G[pos]*(pos-l)+f[r]-f[pos]-F[pos]*(r-pos);
output(ans);
}
finish();
return 0;
}