\(mxb\) 为历史最大值，\(tg1,tg2,tg3,tg4\) 分别对应最大值真实 \(tag\) ，其他值真实 \(tag\) ，最大值最大 \(tag\) ，其它值最大 \(tag\)
#include<bits/stdc++.h>
using namespace std;
#define N 500005
#define int long long
int n,m;
int a[N];
struct TREE{
int sum[N*4],mxb[N*4],mx1[N*4],cnt[N*4],mx2[N*4],tot[N*4];
int tg1[N*4],tg2[N*4],tg3[N*4],tg4[N*4];
void up(int p){
int ls=p*2,rs=p*2+1;
sum[p]=sum[ls]+sum[rs];
mxb[p]=max(mxb[ls],mxb[rs]);
if(mx1[ls]==mx1[rs]){
mx1[p]=mx1[ls],cnt[p]=cnt[ls]+cnt[rs];
mx2[p]=max(mx2[ls],mx2[rs]);
}
else if(mx1[ls]>mx1[rs]){
mx1[p]=mx1[ls],cnt[p]=cnt[ls];
mx2[p]=max(mx2[ls],mx1[rs]);
}
else{
mx1[p]=mx1[rs],cnt[p]=cnt[rs];
mx2[p]=max(mx2[rs],mx1[ls]);
}
}
void upd(int p,int t1,int t2,int t3,int t4){
sum[p]+=t1*cnt[p]+t2*(tot[p]-cnt[p]);
mxb[p]=max(mxb[p],mx1[p]+t3);
mx1[p]+=t1;
if(mx2[p]!=-2e9) mx2[p]+=t2;
tg3[p]=max(tg3[p],tg1[p]+t3),tg1[p]+=t1;
tg4[p]=max(tg4[p],tg2[p]+t4),tg2[p]+=t2;
}
void down(int p){
int t1=tg1[p],t2=tg2[p],t3=tg3[p],t4=tg4[p],ls=p*2,rs=p*2+1;
int mx=max(mx1[ls],mx1[rs]);
if(mx==mx1[ls]) upd(ls,t1,t2,t3,t4);
else upd(ls,t2,t2,t4,t4);
if(mx==mx1[rs]) upd(rs,t1,t2,t3,t4);
else upd(rs,t2,t2,t4,t4);
tg1[p]=tg2[p]=tg3[p]=tg4[p]=0;
}
void build(int p,int l,int r){
tot[p]=r-l+1;
if(l==r){
sum[p]=mxb[p]=mx1[p]=a[l];
mx2[p]=-2e9,cnt[p]=1;
return ;
}
int mid=(l+r)>>1;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
up(p);
}
void add(int p,int l,int r,int x,int y,int z){
if(x<=l&&r<=y){
sum[p]+=z*(r-l+1),mx1[p]+=z,mxb[p]=max(mxb[p],mx1[p]);
tg1[p]+=z,tg3[p]=max(tg3[p],tg1[p]);
tg2[p]+=z,tg4[p]=max(tg4[p],tg2[p]);
if(mx2[p]!=-2e9) mx2[p]+=z;
return ;
}
down(p);
int mid=(l+r)>>1;
if(x<=mid) add(p*2,l,mid,x,y,z);
if(mid<y) add(p*2+1,mid+1,r,x,y,z);
up(p);
}
void qmn(int p,int l,int r,int x,int y,int z){
if(z>=mx1[p]) return ;
if(x<=l&&r<=y&&z>mx2[p]){
sum[p]-=cnt[p]*(mx1[p]-z);
tg1[p]-=(mx1[p]-z),mx1[p]=z;//tg3²»¸üÐÂÊÇÒòΪֻ»á¼õÉÙ
return ;
}
down(p);
int mid=(l+r)>>1;
if(x<=mid) qmn(p*2,l,mid,x,y,z);
if(mid<y) qmn(p*2+1,mid+1,r,x,y,z);
up(p);
}
int sum_(int p,int l,int r,int x,int y){
if(x<=l&&r<=y) return sum[p];
down(p);
int mid=(l+r)>>1,ans=0;
if(x<=mid) ans+=sum_(p*2,l,mid,x,y);
if(mid<y) ans+=sum_(p*2+1,mid+1,r,x,y);
return ans;
}
int maxa(int p,int l,int r,int x,int y){
if(x<=l&&r<=y) return mx1[p];
down(p);
int mid=(l+r)>>1,ans=-2e9;
if(x<=mid) ans=max(ans,maxa(p*2,l,mid,x,y));
if(mid<y) ans=max(ans,maxa(p*2+1,mid+1,r,x,y));
return ans;
}
int maxb(int p,int l,int r,int x,int y){
if(x<=l&&r<=y) return mxb[p];
down(p);
int mid=(l+r)>>1,ans=-2e9;
if(x<=mid) ans=max(ans,maxb(p*2,l,mid,x,y));
if(mid<y) ans=max(ans,maxb(p*2+1,mid+1,r,x,y));
return ans;
}
}T;
signed main(){
scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
T.build(1,1,n);
while(m--){
int op,x,y,z;
scanf("%lld%lld%lld",&op,&x,&y);
if(op<=2) scanf("%lld",&z);
if(op==1) T.add(1,1,n,x,y,z);
if(op==2) T.qmn(1,1,n,x,y,z);
if(op==3) printf("%lld\n",T.sum_(1,1,n,x,y));
if(op==4) printf("%lld\n",T.maxa(1,1,n,x,y));
if(op==5) printf("%lld\n",T.maxb(1,1,n,x,y));
}
return 0;
}