如题

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1145141;
int a[N],maxn[N*4],n,m,k;
struct node
{
	int maxn,tag,tag1,p;
}tr[N*4];
void build(int root,int l,int r)
{
	tr[root].tag=tr[root].p=tr[root].tag1=0;
	if(l==r) tr[root].maxn=a[l];
	else 
	{
		int mid=(l+r)>>1;
		build(root*2,l,mid);
		build(root*2+1,mid+1,r);
		tr[root].maxn=max(tr[root*2].maxn,tr[root*2+1].maxn);
	}
}
void pushdown(int root,int l,int r)
{
	if(tr[root].p)
	{
		tr[root*2].maxn=tr[root].tag1,tr[root*2+1].maxn=tr[root].tag1;
		tr[root*2].tag1=tr[root].tag1,tr[root*2+1].tag1=tr[root].tag1;
		tr[root*2].p=tr[root*2+1].p=1;
		tr[root].p=tr[root].tag1=0;
	}
	if(tr[root].tag)
	{
		tr[root*2].tag+=tr[root].tag,tr[root*2+1].tag+=tr[root].tag;
		tr[root*2].maxn+=tr[root].tag,tr[root*2+1].maxn+=tr[root].tag;
		tr[root].tag=0;
	}
}
int query(int root,int ql,int qr,int l,int r)
{
	int ans=-1e16;
	if(ql<=l&&r<=qr) return tr[root].maxn;
	int mid=(l+r)>>1;
	pushdown(root,l,r);
	if(ql<=mid) ans=query(root*2,ql,qr,l,mid);
	if(qr>mid) ans=max(ans,query(root*2+1,ql,qr,mid+1,r));
	return ans;
}
void update1(int root,int ul,int ur,int l,int r,int add)
{
	if(l>=ul&&r<=ur)
	{
		tr[root].tag1=add;
		tr[root].p=1;
		tr[root].tag=0;
		tr[root].maxn=add;
		return ;
	}
	pushdown(root,l,r);
	int mid=(l+r)>>1;
	if(ul<=mid) update1(root*2,ul,ur,l,mid,add);
	if(ur>mid) update1(root*2+1,ul,ur,mid+1,r,add);
}
void update2(int root,int ul,int ur,int l,int r,int add)
{
	if(l>=ul&&r<=ur)
	{
		tr[root].tag+=add,tr[root].maxn+=add;
		return ; 
	}
	pushdown(root,l,r);
	int mid=(l+r)>>1;
	if(ul<=mid) update2(root*2,ul,ur,l,mid,add);
	if(ur>mid) update2(root*2+1,ul,ur,mid+1,r,add);
	tr[root].maxn=max(tr[root*2].maxn,tr[root*2+1].maxn);
}
signed main()
{
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
	build(1,1,n);
	while(m--)
	{
		int pd,x,y;
		scanf("%lld%lld%lld",&pd,&x,&y);
		if(pd==1)
		{
			scanf("%lld",&k);
			update1(1,x,y,1,n,k);
		}
		else if(pd==2)
		{
			scanf("%lld",&k);
			update2(1,x,y,1,n,k);
		}
		else printf("%lld\n",query(1,x,y,1,n));
	}
}