50PTS求条，WAon#6789 TLEon#10

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
struct node
{
	int l;
	int r;
	int v;
	int lzy;
	int op;
};
node tr[N*4];
int a[N];
void pushup(int u)
{
	tr[u].v=max(tr[u*2].v,tr[u*2+1].v);
}
void pushdown(int u)
{
	int v=tr[u].v;
	int lzy=tr[u].lzy;
	int op=tr[u].op;
	if(op!=-1)
	{
		if(op==1)
		{
			if(tr[u*2].op!=-1)
			{
				tr[u*2].v+=lzy;
				tr[u*2].lzy+=lzy;				
			}
			else
			{
				tr[u*2].v+=lzy;
				tr[u*2].lzy+=lzy;				
				tr[u*2].op=op;				
			}					
			if(tr[u*2+1].op!=-1)
			{
				tr[u*2+1].v+=lzy;
				tr[u*2+1].lzy+=lzy;				
			}
			else
			{
				tr[u*2+1].v+=lzy;
				tr[u*2+1].lzy+=lzy;				
				tr[u*2+1].op=op;				
			}	
			tr[u].lzy=0;
			tr[u].op=-1;
		}
		if(op==2)
		{
			tr[u*2].v=lzy;
			tr[u*2].lzy=lzy;
			tr[u*2].op=op;
			tr[u*2+1].v=lzy;
			tr[u*2+1].lzy=lzy;
			tr[u*2+1].op=op;
			tr[u].lzy=0;
			tr[u].op=-1;
		}
	}
}
void bui(int u,int l,int r)
{
	tr[u].l=l;tr[u].r=r;tr[u].v=0;tr[u].lzy=0;tr[u].op=-1;
	if(l==r)
	{
		tr[u].v=a[l];
		return ;
	}
	int mid=(l+r)/2;
	bui(u*2,l,mid);
	bui(u*2+1,mid+1,r);
	pushup(u);
}
int query(int u,int l,int r)
{		
	if(tr[u].l>=l&&tr[u].r<=r)
	{		
		return tr[u].v;		
	}
	pushdown(u);
	int mid=(tr[u].l+tr[u].r)/2;
	int tmp1=-INT_MAX,tmp2=-INT_MAX;
	if(l<=mid)
		tmp1=query(u*2,l,r);
	if(r>mid)
		tmp2=query(u*2+1,l,r);
	int k=max(tmp1,tmp2);
	return k;
}
void mdf1(int u,int l,int r,int x)
{
	if(tr[u].l>=l&&tr[u].r<=r)
	{
		if(tr[u].op!=-1)
		{
			tr[u].v+=x;
			tr[u].lzy+=x;
		}
		else
		{
			tr[u].v+=x;
			tr[u].lzy+=x;				
			tr[u].op=1;	
		}
	}
	else
	{
		pushdown(u);
		int mid=(tr[u].l+tr[u].r)/2;
		if(l<=mid)
			mdf1(u*2,l,r,x);
		if(r>mid)
			mdf1(u*2+1,l,r,x);
		pushup(u);
	}
}
void mdf2(int u,int l,int r,int x)
{	
	if(tr[u].l>=l&&tr[u].r<=r)
	{
		tr[u].v=x;
		tr[u].lzy=x;
		tr[u].op=2;
	}
	else
	{
		pushdown(u);
		int mid=(tr[u].l+tr[u].r)/2;
		if(l<=mid)
			mdf2(u*2,l,r,x);
		if(r>mid)
			mdf2(u*2+1,l,r,x);
		pushup(u);
	}
}
int main()
{
	cin.tie(0);
	cout.tie(0);
	int n,q;
	cin>>n>>q;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	bui(1,1,n);
	int op;
	while(q--)
	{
		cin>>op;
		if(op==1)
		{
			int l,r,x;
			cin>>l>>r>>x;
			mdf2(1,l,r,x);
		}
		if(op==2)
		{
			int l,r,x;
			cin>>l>>r>>x;
			mdf1(1,l,r,x);
		}
		if(op==3)
		{
			int l,r;
			cin>>l>>r;
			cout<<query(1,l,r)<<endl;
		}
	}
	return 0;
}