rt.题目

#include <bits/stdc++.h>
#define int long long
using namespace std;
inline int ls(int n){return n<<1;}
inline int rs(int n){return n<<1|1;}
int n,m,x,y,z,w,a[1000001],sg[4000001],add[4000001],val[4000001];
inline void pushup(int p){
    sg[p]=max(sg[ls(p)],sg[rs(p)]);
}
inline void pushdown(int p){
    if(val[p]!=2e9){
        sg[ls(p)]=sg[rs(p)]=val[ls(p)]=val[rs(p)]=val[p];
        add[ls(p)]=add[rs(p)]=0;
        val[p]=2e9;
    }
    if(add[p]){
        add[ls(p)]+=add[p];
        add[rs(p)]+=add[p];
        sg[ls(p)]+=add[p];
        sg[rs(p)]+=add[p];
        add[p]=0;
    }
}
void build(int p,int l,int r){
    val[p]=2e9;
	if(l==r){
		sg[p]=a[l];
		return ;
	}
    int mid=l+r>>1;
	build(ls(p),l,mid);
	build(rs(p),mid+1,r); 
	pushup(p);
}
void change(int p,int l,int r,int x,int y,int v){
    if(x<=l&&r<=y){
        sg[p]=val[p]=v;
        add[p]=0;
        return;
    }
    pushdown(p);
    int mid=l+r>>1;
    if(x<=mid)change(ls(p),l,mid,x,y,v);
    if(y>mid)change(rs(p),mid+1,r,x,y,v);
    pushup(p);
}
void addn(int p,int l,int r,int x,int y,int v){
    if(x<=l&&r<=y){
        sg[p]+=v;
        add[p]+=v;
        return;
    }
    pushdown(p);
    int mid=l+r>>1;
    if(x<=mid)addn(ls(p),l,mid,x,y,v);
    if(y>mid)addn(rs(p),mid+1,r,x,y,v);
    pushup(p);
}
int maxn(int p,int l,int r,int x,int y){
	if(l>=x&&r<=y)return sg[p];
    pushdown(p);
	int ans=-2e9,mid=l+r>>1;
	if(x<=mid)ans=max(ans,maxn(ls(p),l,mid,x,y));
	if(y>mid)ans=max(ans,maxn(rs(p),mid+1,r,x,y));
	return ans;
}
signed main(){
	cin>>n>>m;
    for(int i=1;i<=n;i++)cin>>a[i];
	build(1,1,n);
	for(int i=1;i<=m;i++){
		scanf("%lld%lld%lld",&x,&y,&z);
        switch(x){
            case 1:scanf("%lld",&w),change(1,1,n,y,z,w);break;
            case 2:scanf("%lld",&w),addn(1,1,n,y,z,w);break;
            case 3:printf("%lld\n",maxn(1,1,n,y,z));break;
        }
	}
}