代码

#include<bits/stdc++.h>
#include<algorithm>
#define int long long
typedef long long lli;
typedef double lf;
using namespace std;
const lli MAX_=-LONG_LONG_MAX;
lli n,block,tot;
lli a[1003007];
lli l[100007],r[100007],be[1003007],lazy[100007],mx[100007];
void build()
{
	for(int i=0;i<=100005;i++)mx[i]=MAX_;
	block=sqrt(n),tot=n/block;
	if(n%block)tot++;
	for(int i=1;i<=tot;i++)
		l[i]=(i-1)*block+1,r[i]=i*block;
	r[tot]=n;
	for(int i=1;i<=n;i++)
		be[i]=(i-1)/block+1;
	for(int i=1;i<=tot;i++)
		for(int j=l[i];j<=r[i];j++)
			mx[i]=max(mx[i],a[j]);
}
void upd(int x,int y,lli k)
{
	if(be[x]==be[y])
	{
		for(int i=x;i<=y;i++)
			a[i]+=k,mx[be[i]]=max(mx[be[i]],a[i]+lazy[be[i]]);
		return;
	}
	for(int i=x;i<=r[be[x]];i++)
		a[i]+=k,mx[be[i]]=max(mx[be[i]],a[i]+lazy[be[i]]);
	for(int i=l[be[y]];i<=y;i++)
		a[i]+=k,mx[be[i]]=max(mx[be[i]],a[i]+lazy[be[i]]);
	for(int i=be[x]+1;i<=be[y]-1;i++)
		lazy[i]+=k,mx[i]+=k;
}
void cover_(int x,int y,lli k)
{
	if(be[x]==be[y])
	{
		for(int i=x;i<=y;i++)
			a[i]=k-lazy[be[i]];
		mx[be[x]]=max(mx[be[x]],k);
		return;
	}
	for(int i=x;i<=r[be[x]];i++)
		a[i]=k-lazy[be[i]];
	mx[be[x]]=max(mx[be[x]],k);
	for(int i=l[be[y]];i<=y;i++)
		a[i]=k-lazy[be[i]];
	mx[be[y]]=max(mx[be[y]],k);
	for(int i=be[x]+1;i<=be[y]-1;i++)
		lazy[i]=k-a[i],mx[i]=k;
}
lli query(int x,int y)
{
	lli mx1=MAX_;
	if(be[x]==be[y])
	{
		for(int i=x;i<=y;i++)
			mx1=max(mx1,a[i]+lazy[be[i]]);	
		return mx1;
	}
	for(int i=x;i<=r[be[x]];i++)
		mx1=max(mx1,a[i]+lazy[be[i]]);
	for(int i=l[be[y]];i<=y;i++)
		mx1=max(mx1,a[i]+lazy[be[i]]);
	for(int i=be[x]+1;i<=be[y]-1;i++)
		mx1=max(mx1,mx[i]);
	return mx1;
}
signed main()
{
    ios::sync_with_stdio(0);
 	cin.tie(0),cout.tie(0);
 	//freopen("P1253_6.in","r",stdin);
 	//freopen("fout.txt","w",stdout);
 	int q;
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
	build();
	while(q--)
	{
		lli x,y,k,op;
		scanf("%lld%lld%lld",&op,&x,&y);
		if(op==3)
			printf("%lld\n",query(x,y));
		else if(op==2)
		{
			scanf("%lld",&k);
			upd(x,y,k);
		}
		else 
		{
			scanf("%lld",&k);
			cover_(x,y,k);
		}/*
		for(int i=1;i<=n;i++)
			cout<<a[i]+lazy[be[i]]<<" ";
		cout<<endl;
		for(int i=1;i<=tot;i++)
			cout<<mx[i]<<" ";
		cout<<endl;*/
	}
}