90分平衡树求卡常

#include<bits/stdc++.h>
#define int long long
using namespace std;
struct Node{
	int ls,rs,p,size;
	int x;
	int ma;
	int add_tag,change_tag;
}t[1000010];
int root,cnt,n,m;
inline int New(int x){
	cnt++;
	t[cnt].x=x;
	t[cnt].p=rand();
	t[cnt].size=1;
	t[cnt].ma=x;
	t[cnt].change_tag=-1000000010;
	return cnt;
}
inline void Updata(int u){
	t[u].size=t[t[u].ls].size+1+t[t[u].rs].size;
	t[u].ma=t[u].x;
	if(t[u].ls) t[u].ma=max(t[u].ma,t[t[u].ls].ma);
	if(t[u].rs) t[u].ma=max(t[u].ma,t[t[u].rs].ma);
}
inline void add(int u,int x){
	t[u].add_tag+=x;
	t[u].ma+=x;
	t[u].x+=x;
}
inline void change(int u,int x){
	t[u].add_tag=0;
	t[u].change_tag=x;
	t[u].ma=x;
	t[u].x=x;
}
inline void push_down(int u){
	if(t[u].change_tag!=-1000000010){
		if(t[u].ls) change(t[u].ls,t[u].change_tag);
		if(t[u].rs) change(t[u].rs,t[u].change_tag);
		t[u].change_tag=-1000000010;
	}
	if(t[u].add_tag){
		if(t[u].ls) add(t[u].ls,t[u].add_tag);
		if(t[u].rs) add(t[u].rs,t[u].add_tag);
		t[u].add_tag=0;
	}
}
inline void Split(int u,int k,int &L,int &R){
	if(u==0){
		L=R=0;
		return;
	}
	push_down(u);
	if(t[t[u].ls].size+1<=k){
		L=u;
		Split(t[u].rs,k-t[t[u].ls].size-1,t[u].rs,R);
	}
	else{
		R=u;
		Split(t[u].ls,k,L,t[u].ls);
	}
	Updata(u);
}
inline int Merge(int L,int R){
	if(!L||!R) return L+R;
	if(t[L].p>t[R].p){
		push_down(L);
		t[L].rs=Merge(t[L].rs,R);
		Updata(L);
		return L;
	}
	else{
		push_down(R);
		t[R].ls=Merge(L,t[R].ls);
		Updata(R);
		return R;
	}
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	//freopen(".in","r",stdin);
	//freopen(".out","w",stdout);
	srand(time(NULL));
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		int x;
		cin>>x;
		root=Merge(root,New(x));
	}
	while(m--){
		int op,l,r,x;
		int L,R,p;
		cin>>op>>l>>r;
		Split(root,r,L,R);
		Split(L,l-1,L,p);
		if(op==1){
			cin>>x;
			change(p,x);
		}
		if(op==2){
			cin>>x;
			add(p,x);
		}
		if(op==3){
			cout<<t[p].ma<<"\n";
		}
		root=Merge(Merge(L,p),R);
	}
	return 0;
}