#10RE数组开200005后MLE#10

#include<iostream>

using namespace std;
typedef long long ll;

int n,q;
ll t[800005],lazyj[800005],lazyg[800005],a[100005];
bool is[800005];
ll build(int left,int right,int fa)
{
	if(left==right)return t[fa]=a[left];
	int mid=(left+right)>>1;
	return t[fa]=max(build(left,mid,fa<<1),build(mid+1,right,fa<<1|1));
}
void push_back(int fa)
{
	if(is[fa])
	{
		t[fa<<1|1]=t[fa<<1]=lazyg[fa];
		lazyj[fa<<1|1]=lazyj[fa<<1]=0;
		lazyg[fa<<1|1]=lazyg[fa<<1]=lazyg[fa];
		is[fa<<1]=is[fa<<1|1]=1;
		is[fa]=0;
	}
	t[fa<<1]+=lazyj[fa];
	t[fa<<1|1]+=lazyj[fa];
	lazyj[fa<<1]+=lazyj[fa];
	lazyj[fa<<1|1]+=lazyj[fa];
	lazyj[fa]=0;
}

ll query(int ql,int qr,int left,int right,int fa)
{
	if(ql<=left&&qr>=right)return t[fa];
	int mid=(left+right)>>1;
	ll ans=-0x7f7f7f7f7f7f7f7f;//
	push_back(fa);
	if(ql<=mid)ans=max(ans,query(ql,qr,left,mid,fa<<1));
	if(qr>mid)ans=max(ans,query(ql,qr,mid+1,right,fa<<1|1));
	return ans;
}

void update(int ql,int qr,int left,int right,int fa,ll k)
{
	if(ql<=left&&qr>=right)
	{
		t[fa]+=k;
		lazyj[fa]+=k;
		return;
	}
	int mid=(left+right)>>1;
	push_back(fa);
	if(ql<=mid)update(ql,qr,left,mid,fa<<1,k);
	if(qr>mid)update(ql,qr,mid+1,right,fa<<1|1,k);
	t[fa]=max(t[fa<<1],t[fa<<1|1]);
}
void reset(int ql,int qr,int left,int right,int fa,ll k)
{
	if(ql<=left&&qr>=right)
	{
		t[fa]=k;
		lazyj[fa]=0;
		lazyg[fa]=k;
		is[fa]=1;
		return ;
	}
	int mid=(left+right)>>1;
	push_back(fa);
	if(ql<=mid)reset(ql,qr,left,mid,fa<<1,k);
	if(qr>mid)reset(ql,qr,mid+1,right,fa<<1|1,k);
	t[fa]=max(t[fa<<1],t[fa<<1|1]);
}
int main()
{
	scanf("%d%d",&n,&q);
	for(int i=1;i<=n;i++)scanf("%lld",&a[i]);
	build(1,n,1);
	for(int i=1;i<=q;i++)
	{
		int type,tt1,tt2;
		scanf("%d%d%d",&type,&tt1,&tt2);
		if(type==1)
		{
			ll tt3;
			scanf("%lld",&tt3);
			reset(tt1,tt2,1,n,1,tt3);
		}
		else if(type==2)
		{
			ll tt3;
			scanf("%lld",&tt3);
			update(tt1,tt2,1,n,1,tt3);
		}
		else{
			printf("%lld\n",query(tt1,tt2,1,n,1));
		}
	}
	return 0;
}

RE记录
MLE记录