```cpp
#include<algorithm>
#include<iostream>
#include<cstdio>
#include<vector>
#define foir(i,l,r) for (register int i=l;i<=r;++i)
#define fopr(i,l,r) for (register int i=l;i>=r;--i)
#define maxn 1000010
#define inf 0x3f3f3f3f
#define int long long
using namespace std;
inline int read()
{
int x=0; bool f=0; char c=getchar();
while (!isdigit(c)) f|=c=='-', c=getchar();
while (isdigit(c)) x=(x<<1)+(x<<3)+(c^48), c=getchar();
return f?-x:x;
}
int t[maxn*40],tag[maxn*40];
int ls[maxn*40],rs[maxn*40];
int rt[maxn<<2];
int tgrt[maxn<<2];
bool col[maxn*40];
int cnt;
int n,m;
int a[maxn];
int nxt[maxn],pre[maxn];
struct Segment_tree
{
inline void pushup(int p)
{
t[p]=0;
if (ls[p]) t[p]+=t[ls[p]];
if (rs[p]) t[p]+=t[rs[p]];
}
inline void pushdown(int L,int R,int p)
{
if (!tag[p]) return ;
int mid=(L+R)>>1;
if (!ls[p]) ls[p]=++cnt;
if (!rs[p]) rs[p]=++cnt;
if (col[ls[p]]) t[ls[p]]=tag[ls[p]]=col[ls[p]]=0;
if (col[rs[p]]) t[rs[p]]=tag[rs[p]]=col[rs[p]]=0;
t[ls[p]]+=(mid-L+1)*tag[p], tag[ls[p]]+=tag[p];
t[rs[p]]+=(R-mid)*tag[p], tag[rs[p]]+=tag[p];
tag[p]=0;
}
void update(int L,int R,int ql,int qr,int k,int &p)
{
if (!p) p=++cnt;
if (ql<=L&&R<=qr) return t[p]+=(R-L+1)*k, tag[p]+=k, void();
int mid=(L+R)>>1; pushdown(L,R,p);
if (ql<=mid) update(L,mid,ql,qr,k,ls[p]);
if (qr>mid) update(mid+1,R,ql,qr,k,rs[p]);
pushup(p);
}
int query(int L,int R,int ql,int qr,int p)
{
if (!p) return 0;
if (ql<=L&&R<=qr) return t[p];
int mid=(L+R)>>1,res=0; pushdown(L,R,p);
if (ql<=mid) res+=query(L,mid,ql,qr,ls[p]);
if (qr>mid) res+=query(mid+1,R,ql,qr,rs[p]);
pushup(p);
return res;
}
};
struct twoD_seg
{
Segment_tree tr[maxn<<2];
Segment_tree tg[maxn<<2];
int RE=0;
void solve(int L,int R,int k,int p,int o,int &nodep,int nodeo)
{
// cout<<"solve:"<<L<<" "<<R<<" "<<nodep<<" "<<nodeo<<endl;
// ++RE;
// if (RE>10) return ;
if (!nodeo) return ;
if (!nodep) nodep=++cnt;
t[nodep]+=k*t[nodeo];
if (L==R) return ;
int mid=(L+R)>>1; tg[o].pushdown(L,R,nodeo);
solve(L,mid,k,p,o,ls[nodep],ls[nodeo]);
solve(mid+1,R,k,p,o,rs[nodep],rs[nodeo]);
}
inline void pushdown(int L,int R,int p)
{
if (!t[tgrt[p]]) return ;
int mid=(L+R)>>1;
// cout<<tgrt[p<<1]<<" "<<tgrt[p]<<endl;
solve(1,n,1,p<<1,p,tgrt[p<<1],tgrt[p]);
solve(1,n,1,p<<1|1,p,tgrt[p<<1|1],tgrt[p]);
solve(1,n,L-mid+1,p<<1,p,rt[p<<1],tgrt[p]);
solve(1,n,R-mid,p<<1|1,p,rt[p<<1|1],tgrt[p]);
t[tgrt[p]]=tag[tgrt[p]]=0; col[ls[tgrt[p]]]=col[rs[tgrt[p]]]=1;
}
void update(int L,int R,int ql,int qr,int qll,int qrr,int k,int p)
{
if (ql<=L&&R<=qr)
{
tg[p].update(1,n,qll,qrr,k,tgrt[p]);
tr[p].update(1,n,qll,qrr,k*(R-L+1),rt[p]);
return ;
}
tr[p].update(1,n,qll,qrr,k*(min(R,qr)-max(L,ql)+1),rt[p]);
int mid=(L+R)>>1; pushdown(L,R,p);
if (ql<=mid) update(L,mid,ql,qr,qll,qrr,k,p<<1);
if (qr>mid) update(mid+1,R,ql,qr,qll,qrr,k,p<<1|1);
}
int query(int L,int R,int ql,int qr,int qll,int qrr,int p)
{
if (ql<=L&&R<=qr) return tr[p].query(1,n,qll,qrr,rt[p]);
int mid=(L+R)>>1,res=0; pushdown(L,R,p); //tr[p].query(1,n,qll,qrr,rt[p])*(min(R,qr)-max(L,ql)+1);
if (ql<=mid) res+=query(L,mid,ql,qr,qll,qrr,p<<1);
if (qr>mid) res+=query(mid+1,R,ql,qr,qll,qrr,p<<1|1);
return res;
}
}seg;
struct node
{
int L,R;
int w;
int x;
bool operator < (const node &p) const
{
if (x!=p.x) return x<p.x;
else return w<p.w;
}
node(int LL=0,int RR=0,int W=0,int X=0) { L=LL, R=RR, w=W, x=X; }
}tp[maxn];
namespace prework
{
inline bool cmp(node A,node B) { return A.w<B.w; }
inline void init()
{
n=read(),m=read();
foir(i,1,n)
a[i]=read();
a[0]=a[n+1]=-100000000000;
foir(i,1,n)
{
pre[i]=i-1;
while (pre[i]&&a[pre[i]]>=a[i])
pre[i]=pre[pre[i]];
}
fopr(i,n,1)
{
nxt[i]=i+1;
while (nxt[i]<=n&&a[nxt[i]]>=a[i])
nxt[i]=nxt[nxt[i]];
}
}
inline void main()
{
init();
foir(i,1,n) tp[i]=node(pre[i]+1,nxt[i]-1,i,a[i]);
sort(tp+1,tp+1+n);
foir(i,1,n)
{
if (tp[i].x==tp[i-1].x&&tp[i].L==tp[i-1].L&&tp[i].R==tp[i-1].R)
tp[i-1].R=tp[i-1].w, tp[i].L=tp[i-1].w+1;
seg.update(1,n,tp[i].L,tp[i].w,tp[i].w,tp[i].R,tp[i].x,1);
}
// foir(i,1,n) cout<<tp[i].L<<" "<<tp[i].w<<" "<<tp[i].R<<" "<<tp[i].x<<endl;
return void();
}
}
signed main()
{
prework::main();
while (m--)
{
int ll=read(), rr=read();
cout<<seg.query(1,n,ll,rr,ll,rr,1)<<endl;
}
return 0;
}
/*
6 1
1 3 2 4 2 6
3 6
5 5
5 2 4 1 3
1 5
1 3
2 4
3 5
2 5
*/
```
by Ckger @ 2021-11-15 20:20:29
太简单了！我随便切。但是你太弱了，我不屑于教你。
by 九分裤宝宝 @ 2021-11-15 20:44:50
这玩意复杂度完完全全就是假的，没救
by FunnyCreatress @ 2021-11-15 20:55:52
@[FunnyCreatress](/user/77174) 为啥,不懂
by Ckger @ 2021-11-15 20:57:29
@[FunnyCreatress](/user/77174) 大佬教教我
by Ckger @ 2021-11-15 21:04:04
@[Ckger](/user/215590) 反正矩形加矩形求和之类的东西用二维线段树复杂度非常不靠谱，现有的写法基本上都可以卡成 $n^2$，根本原因是一维上的拆分方式会影响到另一维导致lazytag复杂度退化
by FunnyCreatress @ 2021-11-15 21:15:00
矩阵加矩阵求和直接 CDQ 吧。树套树 / 二维线段树无法处理标记下放。
by MuYC @ 2021-11-15 21:16:29
@[MuYC](/user/67817) 草，被机房dalao坑了（他说可以直接传标记），谢谢学长！
by Ckger @ 2021-11-15 21:32:06
@[Ckger](/user/215590) 没事，我也是省队集训的时候被自己蠢到了才发现的。
by MuYC @ 2021-11-15 21:43:16
@[Ckger](/user/215590) 你还没吸取我考场爆成 65 pts 的经验么
by __OccDreamer__ @ 2021-11-16 09:18:24