Description
给定长度为$n$的序列：$a_1,a_2,cdots ,a_n$，记为$a[1:n]$。类似地，$a[l:r](1 leq lleq rleq N)$是指序列：$a_l,a_{l+1},cdots,a_{r-1},a_r$。若$1leq lleq sleq tleq rleq n$，则称$a[s:t]$是$a[l:r]$的子序列。现在有$q$个询问，每个询问给定两个数$l$和$r$，$1leq lleq rleq n$，求$a[l:r]$的不同子序列的最小值之和。例如，给定序列$5,2,4,1,3$，询问给定的两个数为$1$和$3$，那么$a[1:3]$有$6$个子序列$a[1:1],a[2:2],a[3:3],a[1:2],a[2:3],a[1:3]$，这$6$个子序列的最小值之和为$5+2+4+2+2+2=17$。
Solution
对于离线的做法，可以使用莫队，考虑从区间$[l,r]$转移至区间$[]l,r+1]$时对答案产生的贡献
这些贡献是以$r+1$为右端点的，左端点在$[l,r+1]$的所有区间最小值之和
设$p$是区间$[l,r+1]$的最小值位置，那么最小值在$p$的答案可以提前算出
设$pre_i$为$i$之前第一个比$a_i$小的数的位置，可以单调栈预处理，设$f_{i}$表示左端点在$[1,i]$，右端点在$r+1$的区间最小值之和，那么
$$f_{i}=a_i(a_i-pre_i)+f_{pre_i}$$
$f_i-f_p$就是剩余的对答案的贡献
对于在线的做法，发现$f_i$也可以代表右端点在$i$，左端点在$[1,i]$的区间最小值之和
对于区间$[l,r]$，先求出$p$，对于$p$右侧的部分，答案即为$f_{p+1}+cdots + f_{r-1}+f_r-(r-p)f_p$，可以使用前缀和$O(1)$求出
对于左侧同理
#include<iostream> #include<cstdio> #include<cmath> using namespace std; int n,q,lg[100005]={-1},minn[100005][21],sta[100005],top,suf[100005],pre[100005]; long long fr[100005],fl[100005],gr[100005],gl[100005],a[100005]; inline int read(){ int f=1,w=0; char ch=0; while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9')w=(w<<1)+(w<<3)+ch-'0',ch=getchar(); return f*w; } int main(){ n=read(),q=read(),a[0]=a[n+1]=0x7f7f7f7f; for(int i=1;i<=n;i++)a[i]=read(),lg[i]=lg[i>>1]+1,minn[i][0]=i; for(int i=1;i<=20;i++)for(int j=1;j+(1<<i)-1<=n;j++)minn[j][i]=a[minn[j][i-1]]<a[minn[j+(1<<(i-1))][i-1]]?minn[j][i-1]:minn[j+(1<<(i-1))][i-1]; for(int i=1;i<=n;i++){ while(top&&a[sta[top]]>a[i])suf[sta[top--]]=i; pre[i]=sta[top],sta[++top]=i; } while(top)suf[sta[top--]]=n+1; for(int i=1;i<=n;i++)fr[i]=fr[pre[i]]+a[i]*(i-pre[i]),gr[i]=gr[i-1]+fr[i]; for(int i=n;i;i--)fl[i]=fl[suf[i]]+a[i]*(suf[i]-i),gl[i]=gl[i+1]+fl[i]; for(;q;q--){ int l=read(),r=read(),p=a[minn[l][lg[r-l+1]]]<a[minn[r-(1<<lg[r-l+1])+1][lg[r-l+1]]]?minn[l][lg[r-l+1]]:minn[r-(1<<lg[r-l+1])+1][lg[r-l+1]]; printf("%lld ",a[p]*(p-l+1)*(r-p+1)+gr[r]-gr[p]-fr[p]*(r-p)+gl[l]-gl[p]-fl[p]*(p-l)); } return 0; }