分析
看到离线区间查询不难想到莫队，则重点在于不同区间之间的转移。
考虑区间([l,r])向区间([l,r+1])的转移。多处的部分应该是([l,r+1],[l+1,r+1]...[r+1,r+1])，算出这一部分的贡献即可。设([l,r])的最小值点为(p)，那么左端点在([l,p])中的所有区间贡献均为(a[p])。显然这个值可以使用rmq算法预处理。
现在算左端点在([p+1,r])中的贡献。我们采取一种划分的思路，把这个区间划分为很多个小区间，每个区间在保证其最大值为右端点的前提下尽量长。换言之，设(pre[i])为第一个在(i)左侧且小于之的数的位置，那么原区间就会被拆成([pre_r,j],[pre_{pre_r},pre_r]...)，对于其中每一段，其贡献都是右端点乘以区间长度。
进一步，设(f[l][r])表示左端点在([l,r])中，右端点为(r)的所有区间的贡献之和，那么有(f[l][r]=f[l][pre_r]+a_r*(r-pre_r))。不难发现，(pre)数组可以通过单调栈求出，而(f)可以省去第一维度并且预处理的。
那么答案的增量就是左侧与右侧之和，也就是(a[p]*(p-l+1)+f[l][r]-f[l][p])。
另外的转移同理。
代码
/*
By Nero Claudius Caeser Augustus Germanicus,
Imperatorum Romanorum.
*/
#include <bits/stdc++.h>
using namespace std;
namespace StandardIO{
template<typename T>void read(T &x){
x=0;T f=1;char c=getchar();
for(; c<'0'||c>'9'; c=getchar()) if(c=='-') f=-1;
for(; c>='0'&&c<='9'; c=getchar()) x=x*10+c-'0';
x*=f;
}
template<typename T>void write(T x){
if(x<0) putchar('-'),x*=-1;
if(x>=10) write(x/10);
putchar(x%10+'0');
}
} using namespace StandardIO;
namespace Project{
#define int long long
const int N=100000+100;
int n,q,block;
int a[N];
struct node{
int l,r,id;
} ask[N];
int top,sta[N],pre[N],suf[N],f1[N],f2[N];
int logg[N],st[N][30],g[N][30];
int l,r,res,ans[N];
void init(){
for(int i=1; i<=n; ++i) st[i][0]=a[i],g[i][0]=i,logg[i]=(i==1)?0:logg[i>>1]+1;
for(int j=1; (1<<j)<=n; ++j){
for(int i=1; i+(1<<j)-1<=n; ++i){
st[i][j]=min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
g[i][j]=st[i][j-1]<st[i+(1<<(j-1))][j-1]?g[i][j-1]:g[i+(1<<(j-1))][j-1];
}
}
}
int query(int l,int r){
int x=logg[r-l+1];
return st[l][x]<st[r-(1<<x)+1][x]?g[l][x]:g[r-(1<<x)+1][x];
}
bool cmp(const node x,const node y){
return (x.l/block!=y.l/block)?(x.l/block<y.l/block):(((x.l/block)&1)?(x.r<y.r):(x.r>y.r));
}
int pr(){
int p=query(l,r);
return f1[r]-f1[p]+a[p]*(p-l+1);
}
int su(){
int p=query(l,r);
return f2[l]-f2[p]+a[p]*(r-p+1);
}
void MAIN(){
read(n),read(q),block=sqrt(q);
for(int i=1; i<=n; ++i) read(a[i]);
init();
for(int i=1; i<=n; ++i){
while(a[sta[top]]>a[i]&&top) suf[sta[top--]]=i;
pre[i]=sta[top],sta[++top]=i;
}
while(top){
pre[sta[top]]=sta[top-1],suf[sta[top--]]=n+1;
}
for(int i=1; i<=n; ++i) f1[i]=f1[pre[i]]+a[i]*(i-pre[i]);
for(int i=n; i>=1; --i) f2[i]=f2[suf[i]]+a[i]*(suf[i]-i);
for(int i=1; i<=q; ++i){
read(ask[i].l),read(ask[i].r),ask[i].id=i;
}
sort(ask+1,ask+q+1,cmp);
l=1,r=0;
for(int i=1; i<=q; ++i){
while(l>ask[i].l) --l,res+=su();
while(r<ask[i].r) ++r,res+=pr();
while(l<ask[i].l) res-=su(),++l;
while(r>ask[i].r) res-=pr(),--r;
ans[ask[i].id]=res;
}
for(int i=1; i<=q; ++i){
write(ans[i]),puts("");
}
}
#undef int
}
int main(){
Project::MAIN();
}