给一篇题解。（下面这张图是从 luogu 上粘贴的，因为不太会画图）
其中纵坐标为 \(t\)，横坐标为 \(a_i\)。
发现同颜色块只有平行四边形和直角梯形（等腰直角三角形）两种情况。
可以将直角梯形削去左下角，分成两部分考虑。
等直可以直接暴力插入区间，总个数 \(O(n)\)。
平行四边形可以看作上三角+中平四/矩形+下三角，矩形不变，平四直接将赋值区间平移即可。
感觉最多有 \(O(n\log n)\) 个区间，加上树状数组应该是 \(O(n\log^2n)\)，但是由于其中 \(dep\) 优化+根本跑不满，所以跑得飞快。
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
int n,dep,a[N],b[N];
int l[N],r[N],ga[N];
int m,tp,st[N],gb[N];
int mx,ans[N],c[N*2][3];
void add(int x,int y,int k){
for(;x<=n*2;x+=x&-x)
c[x][y]+=k;
}int sum(int x,int y){
int re=0;
for(;x;x-=x&-x)
re+=c[x][y];
return re;
}struct node{
int l,r,id;
};vector<node>qu[N];
struct upd{
int id,ad;
};vector<upd>w1[N],w2[N];
signed main(){
ios::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>a[i],mx=max(mx,a[i]);
a[n+1]=mx+1;st[++tp]=n+1;
for(int i=n;i;i--){
while(a[i]>a[st[tp]]) tp--;
r[i]=st[tp];
if(a[i]==a[st[tp]]) st[tp]=i;
else st[++tp]=i;
}tp=0;
for(int i=1;i<=n;i++){
while(tp&&a[i]>=a[st[tp]]) tp--;
if(!st) st[++tp]=i;
else l[i]=st[tp],st[++tp]=i;
}for(int i=1;i<=n;i++)
gb[i]=r[i]-i,dep=max(dep,gb[i]);
for(int i=1;i<=n;i++){
if(!l[i]){
ga[i]=dep-gb[i]+1;
for(int j=ga[i]+1;j<=dep;j++)
w1[j].push_back({j-ga[i]-1+i,a[i]});
}else ga[i]=i-l[i];
}for(int i=1;i<=m;i++){
int t,l,r;cin>>t>>l>>r;
qu[t].push_back({l,r,i});
}for(int i=1;i<=n;i++)
b[i]=max(a[i],b[i-1]),add(i,2,b[i]);
for(int i=dep;i<=n;i++)
for(auto y:qu[i])
ans[y.id]=sum(y.r,2)-sum(y.l-1,2);
for(int i=1;i<=n;i++){
if(ga[i]>=gb[i])
for(int j=1;j<=gb[i];j++){
w1[j].push_back({i+j-1,a[i]});
w1[ga[i]+j].push_back({i+j-1,-a[i]});
}
else for(int j=1;j<=ga[i];j++){
w2[j].push_back({i-j+1,a[i]});
w2[gb[i]+j].push_back({i-j+1,-a[i]});
}
}for(int i=1;i<=dep;i++){
for(auto y:w1[i]) add(y.id,0,y.ad);
for(auto y:w2[i]) add(y.id+n,1,y.ad);
for(auto y:qu[i-1])
ans[y.id]=sum(y.r,0)-sum(y.l-1,0)+sum(y.r-i+1+n,1)-sum(y.l-i+n,1);
}for(int i=1;i<=m;i++) cout<<ans[i]<<"\n";
return 0;
}