分析
莫队。
重点是两个状态怎么 $O(1)$ 的转移。
先来考虑从 $[l+1,r]$ 转移到 $[l,r]$ 的情况。这样子会多出来 $[l,l],[l,l+1],...,[l,r]$ 这些区间，我们来考虑这些区间的答案。
先找到这段区间的最小值 $p$ ，那么右端点在 $[p,r]$ 之间的区间的贡献都是 $a[p]$ 。
还剩下右端点在 $[l,p-1]$ 的情况，把这一部分单独拿出来考虑。
设 $f[i]$ 表示左端点为 $i$ 时，到后面左右位置的贡献。
可以利用单调栈求出右边第一个比 $a[i]$ 小的数，记它的位置为 $R[i]$。
于是可以得到 $f[i]=f[R[i]]+(R[i]-i)\times a[i]$。
然后 $[l,p-1]$ 的贡献就是 $f[l]-f[p]$。
从 $[l,r-1]$ 转移到 $[l,r]$ 的情况同理。
然后就做完了。时间复杂度 $O(n\sqrt{n})$。
具体实现及细节见代码。
代码
//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
typedef long long ll;
using namespace std;
inline int read() {
int X=0,w=1; char c=getchar();
while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
return X*w;
}
const int N=100000+10;
int n,m,block;
int a[N];
struct query { int l,r,id; } q[N];
int sta[N],top=0;
int L[N],R[N];
ll f[N],g[N],ans[N];
int st[20][N],lg[N];
inline int cmp(query a,query b) {
return (a.l/block)^(b.l/block)?a.l<b.l:(((a.l/block)&1)?a.r<b.r:a.r>b.r);
}
inline void build() {
for (re int i=2;i<=n;++i) lg[i]=lg[i>>1]+1;
for (re int i=1;i<=n;++i) st[0][i]=i;
for (re int i=1;i<=lg[n];++i)
for (re int j=1;j+(1<<(i-1))<=n;++j) {
int x=st[i-1][j],y=st[i-1][j+(1<<(i-1))];
st[i][j]=a[x]<=a[y]?x:y;
}
}
inline int query(int l,int r) {
int t=lg[r-l+1],x=st[t][l],y=st[t][r-(1<<t)+1];
return a[x]<=a[y]?x:y;
}
inline ll calcL(int l,int r) {
int p=query(l,r);
return 1ll*(r-p+1)*a[p]+g[l]-g[p];
}
inline ll calcR(int l,int r) {
int p=query(l,r);
return 1ll*(p-l+1)*a[p]+f[r]-f[p];
}
int main() {
n=read(),m=read(),block=sqrt(n);
for (re int i=1;i<=n;++i) a[i]=read();
for (re int i=1;i<=m;++i) q[i].l=read(),q[i].r=read(),q[i].id=i;
sort(q+1,q+m+1,cmp);
//calc L R f g
for (re int i=1;i<=n;++i) {
while (top&&a[sta[top]]>a[i]) --top;
L[i]=sta[top],sta[++top]=i;
}
sta[top=0]=n+1;
for (re int i=n;i>=1;--i) {
while (top&&a[sta[top]]>a[i]) --top;
R[i]=sta[top],sta[++top]=i;
}
for (re int i=1;i<=n;++i) f[i]=f[L[i]]+1ll*(i-L[i])*a[i];
for (re int i=n;i>=1;--i) g[i]=g[R[i]]+1ll*(R[i]-i)*a[i];
//init RMQ
build();
//solve
ll res=0;
for (re int i=1,l=1,r=0;i<=m;++i) {
while (r<q[i].r) res+=calcR(l,++r);
while (l>q[i].l) res+=calcL(--l,r);
while (r>q[i].r) res-=calcR(l,r--);
while (l<q[i].l) res-=calcL(l++,r);
ans[q[i].id]=res;
}
for (re int i=1;i<=m;++i) printf("%lld\n",ans[i]);
return 0;
}