代码

#include <bits/stdc++.h>

using namespace std;
#define lson i*2
#define rson i*2+1
#define int long long
struct st
{
	int l,r;
	int mx;
	int lazyc,lazyp;
}t[4000010];
int a[1000010];
void build(int i,int l,int r)
{
	t[i].lazyc=-1e10,t[i].lazyp=0;
	t[i].l=l,t[i].r=r;
	if(l==r)
	{
		t[i].mx=a[l];
		return ;
	}
	int mid=(l+r)/2;
	build(lson,l,mid);
	build(rson,mid+1,r);
	t[i].mx=max(t[lson].mx,t[rson].mx);
}
void pushdown(int i)
{
	if(t[i].l==t[i].r)
	{
		t[i].lazyc=0,t[i].lazyp=0;
		return ;		
	}	
	if(t[i].lazyc!=-1e10)
	{
		t[lson].mx=t[i].lazyc;
		t[rson].mx=t[i].lazyc;
		t[lson].lazyc=t[i].lazyc;
		t[rson].lazyc=t[i].lazyc;
		t[i].lazyc=0,t[i].lazyp=0;
		return ;
	}
	if(t[i].lazyp==0)
		return ;
	t[lson].mx+=t[i].lazyp;
	t[rson].mx+=t[i].lazyp;
	t[rson].lazyp+=t[i].lazyp;
	t[lson].lazyp+=t[i].lazyp;
	t[i].lazyp=0;
}
void change2(int i,int l,int r,int d)
{
	pushdown(i);
	if(t[i].l>=l&&t[i].r<=r)
	{
		t[i].lazyp=d;
		t[i].mx+=d;
		return ;
	}
	if(t[lson].r>=l)
		change2(lson,l,r,d);
	if(t[rson].l<=r)
		change2(rson,l,r,d);
	t[i].mx=max(t[lson].mx,t[rson].mx);
}
void change1(int i,int l,int r,int d)
{
	pushdown(i);
	if(t[i].l>=l&&t[i].r<=r)
	{
		t[i].lazyc=d;
		t[i].lazyp=0;
		t[i].mx=d;
		return ;
	}
	if(t[lson].r>=l)
		change1(lson,l,r,d);
	if(t[rson].l<r)
		change1(rson,l,r,d);
	t[i].mx=max(t[lson].mx,t[rson].mx);
}
int query(int i,int l,int r)
{
	pushdown(i);
	if(t[i].l>=l&&t[i].r<=r)
		return t[i].mx;
	int e=-1e10;
	if(t[lson].r>=l)
		e=query(lson,l,r);
	if(t[rson].l<=r)
		e=max(query(rson,l,r),e);
	return e;
}
signed main()
{
	int n,m;
	scanf("%lld%lld",&n,&m);
	for(int i=1;i<=n;i++)
		scanf("%lld",&a[i]);
	build(1,1,n);
	int op,x,y,d;
	while(m--)
	{
		scanf("%lld",&op);
		if(op==1)
		{
			scanf("%lld%lld%lld",&x,&y,&d);
			change1(1,x,y,d);
		}
		if(op==2)
		{
			scanf("%lld%lld%lld",&x,&y,&d);
			change2(1,x,y,d);
		}
		if(op==3)
		{
			scanf("%lld%lld",&x,&y);
			printf("%lld\n",query(1,x,y));
		}
	}
	return 0;
}