吉司机线段树

\(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;
}