内測的時候不知道為什麼死活想不出來QAQ。。。。
然後看完題解發現傻逼題。。T_T。。。
yy了一個線段樹做法（僅理論），在區間[l,r]中儲存以mid為中心向兩側的一個單調遞減的數組，空間NlogN，顯然隻有這一個數組中的數對[l,r]的答案有貢獻，然後統計一下字首和二分查找不知道行不行。。。這樣應該是O(Nlog^2N）的。
莫隊就簡單多了。首先用單調棧求出left[i]表示i左邊第一個<=a[i]的數（為了不重不漏要讓right[i]表示i右邊第一個>a[i]的數）。我們發現對于i，(left[i],right[i])為i的勢力範圍。比如加入一個左端點l，我們發現有[l,right[l]),[right[l],right[right[l]])這些的答案發生了變化。顯然這是一個字首和，預處理一下就好了。
但是這是有終止條件的，因為[l,r]中的最小值的right顯然超過了r，把這個特判掉就好了。具體要用rmq求最小值。
AC代碼如下：
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#define N 100005
#define ll long long
using namespace std;
int n,m,a[N],bin[25],f[17][N],q[N],blg[N],lf[N],rg[N],lg2[N];
ll now,ans[N],cl[N],cr[N]; struct node{ int x,y,id; }b[N];
int read(){
int x=0; bool flag=0; char ch=getchar();
while (ch<'0' || ch>'9'){ if (ch=='-') flag=1; ch=getchar(); }
while (ch>='0' && ch<='9'){ x=x*10+ch-'0'; ch=getchar(); }
return flag?-x:x;
}
int rmq(int x,int y){
int k=lg2[y-x+1];
return (a[f[k][x]]<a[f[k][y-bin[k]+1]])?f[k][x]:f[k][y-bin[k]+1];
}
bool cmp(const node &u,const node &v){
return blg[u.x]<blg[v.x] || blg[u.x]==blg[v.x] && u.y<v.y;
}
void mdyl(int l,int r,int k){
int t=rmq(l,r); now+=k*(cr[l]-cr[t]+(ll)a[t]*(r-t+1));
}
void mdyr(int l,int r,int k){
int t=rmq(l,r); now+=k*(cl[r]-cl[t]+(ll)a[t]*(t-l+1));
}
int main(){
n=read(); m=read(); int i,j;
for (i=1; i<=n; i++) a[i]=read();
for (i=1; i<=n; i++) f[0][i]=i;
lg2[1]=0; bin[0]=1; bin[1]=2;
for (i=1; i<=16; i++){
bin[i+1]=bin[i]<<1;
for (j=bin[i]; j<=bin[i+1] && j<=n; j++) lg2[j]=i;
for (j=1; j<=n; j++){
f[i][j]=f[i-1][j];
if (j+bin[i-1]<=n && a[f[i-1][j+bin[i-1]]]<a[f[i][j]])
f[i][j]=f[i-1][j+bin[i-1]];
}
}
a[0]=a[n+1]=-1000000001;
q[j=1]=0;
for (i=1; i<=n; i++){
while (a[i]<a[q[j]]){ rg[q[j]]=i; j--; }
lf[i]=q[j]; q[++j]=i;
}
while (j>1) rg[q[j--]]=n+1;
for (i=1; i<=n; i++) cl[i]=cl[lf[i]]+(ll)a[i]*(i-lf[i]);
for (i=n; i; i--) cr[i]=cr[rg[i]]+(ll)a[i]*(rg[i]-i);
int sz=(int)sqrt(n);
for (i=1; i<=n; i++) blg[i]=(i-1)/sz;
for (i=1; i<=m; i++){
b[i].x=read(); b[i].y=read(); b[i].id=i;
}
sort(b+1,b+m+1,cmp);
int l=1,r=1; now=a[1];
for (i=1; i<=m; i++){
while (l>b[i].x) mdyl(--l,r,1); while (r<b[i].y) mdyr(l,++r,1);
while (l<b[i].x) mdyl(l++,r,-1); while (r>b[i].y) mdyr(l,r--,-1);
ans[b[i].id]=now;
}
for (i=1; i<=m; i++) printf("%lld\n",ans[i]);
return 0;
}
by lych
2016.4.22