考虑我们已经求出了区间 \([l,r]\) 的答案，现在要求 \([l,r+1]\) 的答案。
很明显增多的子序列有 \((l,r+1),(l+1,r+1)...(r+1,r+1)\)。
考虑求出 \([l,r+1]\) 中的最小值的位置 \(p\) （可以用 \(rmq~O(1)\) 求出），那么 \(a_p\) 的贡献就是 \(a_p\times(p-l+1)\)，现在我们只要求出剩下的 \((p+1,r+1),(p+2,r+1)...(r+1,r+1)\) 即可。
考虑 \(DP\)，\(f_{l,r}\) 表示区间 \([l,r]\) 的答案，令 \(pre_i\) 表示第一个比 \(i\) 小的数的位置（没有就是 \(0\)）。易知：\(f_{l,r}=f_{l,pre_r}+a_r\times(r-pre_r)\)，即子序列答案是 \(a_r\) 的和其他的加起来。
、
考虑优化，因为转移只与 \(r\)有关，所以把 \(l\) 这一维去掉，即剩下 \(f_r=f_{pre_r}+a_r\times(r-pre_r)\)。
那么剩下的子序列与 \(f_{r+1}\) 有什么关系呢？先说结论：\((p+1,r+1)...(r+1,r+1)\)的答案就是 \(f_{r+1}-f_p\)。
证明其正确性：\(f_{r+1}\) 表示的就是 \((1,r+1),(2,r+1)...(r+1,r+1)\) 的答案，而且分成一段段，为\(...,(pre_{pre_{r+1}}+1,pre_{r+1}),(pre_{r+1}+1,r)\)，因为 \(a_p\) 是 \([l,r+1]\) 中最小的数，所以这样递归下去，必然出现一个 \(x\) 满足 \(pre_x=p\)，而 \(p\) 即 \(p\) 前面的答案就是\(f_p\)（因为 \(p\) 最小，\((p-j,p)\) 这个子序列的答案等价于 \((p-j,r+1)\)，相减就是 \((p+1,r+1)...(r+1,r+1)\) 了），所以他是正确的。
那么\([l,r+1]\)的增量与处理一下就可以 \(O(1)\) 求出了，其他同理。
上代码：
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const ll N=1e5+50;
ll n,Q,a[N],f[N][20],lg[N],mi[20];
ll pre[N],fr[N],suf[N],fl[N];
ll cmp(ll x,ll y)
{
return a[x]<a[y]?x:y;
}
stack<ll> s;
struct jgt
{
ll l,r,id;
}q[N];
ll b[N],ans[N],sq;
bool cmp1(jgt t1,jgt t2)
{
return (b[t1.l]^b[t2.l])?b[t1.l]<b[t2.l]:((b[t1.l]&1)?t1.r<t2.r:t1.r>t2.r);
}
ll qry(ll l,ll r) {ll t=lg[r-l+1]; return cmp(f[l][t],f[r-mi[t]+1][t]);}
ll right(ll l,ll r) {ll p=qry(l,r); return a[p]*(p-l+1)+fr[r]-fr[p];}
ll left(ll l,ll r) {ll p=qry(l,r); return a[p]*(r-p+1)+fl[l]-fl[p];}
int main()
{
mi[0]=1;
scanf("%lld %lld",&n,&Q);
sq=sqrt(n);
for(ll i=1;i<=n;i++)
{
scanf("%lld",&a[i]);
b[i]=(i-1)/sq+1;
}
for(ll i=1;i<=n;i++)
{
while(!s.empty()&&a[s.top()]>a[i]) s.pop();
if(!s.empty()) pre[i]=s.top();
s.push(i);
}
while(!s.empty()) s.pop();
for(ll i=n;i>=1;i--)
{
suf[i]=n+1;
while(!s.empty()&&a[s.top()]>a[i]) s.pop();
if(!s.empty()) suf[i]=s.top();
s.push(i);
}
for(ll i=1;i<=n;i++)
lg[i]=lg[i-1]+((1<<lg[i-1])==i);
for(ll i=1;i<=n;i++)
lg[i]--;
for(ll i=1;i<=lg[n];i++)
mi[i]=mi[i-1]*2;
for(ll i=1;i<=n;i++)
f[i][0]=i;
for(ll i=1;i<=lg[n];i++)
for(ll j=1;j<=n-mi[i]+1;j++)
f[j][i]=cmp(f[j][i-1],f[j+mi[i-1]][i-1]);
for(ll i=1;i<=n;i++)
fr[i]=fr[pre[i]]+(i-pre[i])*a[i];
for(ll i=n;i>=1;i--)
fl[i]=fl[suf[i]]+(suf[i]-i)*a[i];
for(ll i=1;i<=Q;i++)
{
scanf("%lld %lld",&q[i].l,&q[i].r);
q[i].id=i;
}
sort(q+1,q+Q+1,cmp1);
ll le=1,ri=0,now=0;
for(ll i=1;i<=Q;i++)
{
while(ri<q[i].r) now+=right(le,++ri);
while(le>q[i].l) now+=left(--le,ri);
while(ri>q[i].r) now-=right(le,ri--);
while(le<q[i].l) now-=left(le++,ri);
ans[q[i].id]=now;
}
for(ll i=1;i<=Q;i++)
printf("%lld\n",ans[i]);
return 0;
}