题目：P1253 扶苏的问题

#include<bits/stdc++.h>
#define ll long long 
#define seq(q,w,e) for(int q=w;q<=e;q++)
using namespace std;
const ll maxn=1e5+10;
const ll inf=2e10;
ll a[maxn],tree[maxn<<2],tag1[maxn<<2],tag2[maxn<<2]={-inf};   //tag1数组为加标记，tag2数组为改标记
ll ls(ll p){return p<<1;}
ll rs(ll p){return p<<1|1;}
void push_up(ll p){
   tree[p]=max(tree[ls(p)],tree[rs(p)]);                //维护树
}
void build_tree(ll p,ll pl,ll pr){
   if(pl==pr){
   	tree[p]=a[pl];
   	return;
   }
   ll mid=(pl+pr)>>1;
   build_tree(ls(p),pl,mid);
   build_tree(rs(p),mid+1,pr);
   push_up(p);
}
void add_tag(ll p,ll d){                 //添加加标记，区间加d，可得最大值也加d
   tree[p]+=d;
   tag1[p]+=d;
}
void change_tag(ll p,ll x){              //添加改标记，若有加标记，覆盖
   tree[p]=x;
   tag2[p]=x;
   tag1[p]=0;
}
void push_down(ll p){
   if(tag2[p]!=-inf){                  //若有改标记，先处理改标记
   	change_tag(ls(p),tag2[p]);
   	change_tag(rs(p),tag2[p]);
   	tag2[p]=-inf;
   }//由于在添加改标记时，会清空加标记，所以若同时有加标记都是在修改后添加的
   if(tag1[p]){                        //再处理加标记
   	add_tag(ls(p),tag1[p]);
   	add_tag(rs(p),tag1[p]);
   	tag1[p]=0;
   } 
}
void change(ll l,ll r,ll p,ll pl,ll pr,ll x){
   if(l<=pl&&r>=pr){
   	change_tag(p,x);
   	return;
   }
   push_down(p);
   ll mid=(pl+pr)>>1;
   if(l<=mid) change(l,r,ls(p),pl,mid,x);
   if(r>mid) change(l,r,rs(p),mid+1,pr,x);
   push_up(p);
}
void up_data(ll l,ll r,ll p,ll pl,ll pr,ll d){
   if(l<=pl&&r>=pr){
   	add_tag(p,d);
   	return;
   }
   push_down(p);
   ll mid=(pl+pr)>>1;
   if(l<=mid) up_data(l,r,ls(p),pl,mid,d);
   if(r>mid) up_data(l,r,rs(p),mid+1,pr,d);
   push_up(p);
}
ll query(ll l,ll r,ll p,ll pl,ll pr){
   if(l<=pl&&r>=pr) 
   	return tree[p];
   push_down(p);
   ll mid=(pl+pr)>>1,res1=-inf,res2=-inf;
   if(l<=mid) res1=max(res1,query(l,r,ls(p),pl,mid));
   if(r>mid) res2=max(res2,query(l,r,rs(p),mid+1,pr));
   return max(res1,res2);
}
ll n,m,op;
ll l,r,sum;
signed main(){
   ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
   cin>>n>>m;
   seq(i,1,n){
   	cin>>a[i];
   }
   build_tree(1,1,n);
   seq(i,1,m){
   	cin>>op;
   	if(op==1){
   		cin>>l>>r>>sum;
   		change(l,r,1,1,n,sum);
   	}
   	if(op==2){
   		cin>>l>>r>>sum;
   		up_data(l,r,1,1,n,sum);
   	}
   	if(op==3){
   		cin>>l>>r;
   		cout<<query(l,r,1,1,n)<<"\n";
   	}
   }
   return 0;
}