• 已调试数天

#include<bits/stdc++.h>
using namespace std;
long long n,a,q;
long long dis[8000001],m[8000001][2],ad[8000001][2];
long long read(){
	long long k=0,k1=1;
	char ch=getchar();
	while(!isdigit(ch)){
		if(ch=='-') k1=-1;
		ch=getchar();
	}
	while(isdigit(ch)){
		k=(k<<1)+(k<<3)+(ch^48);
		ch=getchar();
	}
	return k*k1;
}
void upd(long long k,long long x,long long y){
	long long mid=(x+y)/2;
	if(m[k][1]){
		m[k<<1][1]=1;m[k<<1][0]=m[k][0];
		m[k<<1|1][1]=1;m[k<<1|1][0]=m[k][0];
		dis[k]=m[k][0];
		m[k][0]=m[k][1]=0;
		ad[k][0]=ad[k][1]=0;
		ad[k<<1][0]=0;ad[k<<1][1]=-1;
		ad[k<<1|1][0]=0;ad[k<<1|1][1]=-1;
		return;
	}	
	if(ad[k][1]==1){
		ad[k<<1][0]+=ad[k][0];
		ad[k<<1|1][0]+=ad[k][0];
		ad[k<<1][1]=ad[k<<1|1][1]=1;	
		dis[k]+=ad[k][0];
		ad[k][0]=ad[k][1]=0;
	}
	else if(ad[k][1]==-1){
		ad[k<<1][1]=ad[k<<1|1][1]=-1;
		ad[k][0]=ad[k][1]=0;
	}
	return;
}
void adb(long long k,long long x,long long y,long long s,long long e){
	if(x>e||y<e) return;
	if(x==y&&x==e){
		dis[k]=s;
		return;
	}
	long long mid=(x+y)/2;
	adb(k<<1,x,mid,s,e);
	adb(k<<1|1,mid+1,y,s,e);
	dis[k]=max(dis[k<<1],dis[k<<1|1]);
	return;
}
void adm(long long k,long long x,long long y,long long l,long long r,long long s){
	upd(k,x,y);
	if(y<l||x>r) return;
	if(x>=l&&y<=r){
		m[k][0]=s;m[k][1]=1;
		ad[k][0]=0;ad[k][1]=-1;
		dis[k]=s;
		upd(k,x,y);
		return;
	}
	long long mid=(x+y)/2;
	adm(k<<1,x,mid,l,r,s);
	adm(k<<1|1,mid+1,y,l,r,s);
	dis[k]=max(dis[k<<1],dis[k<<1|1]);
	upd(k,x,y);
	return;
}
void add(long long k,long long x,long long y,long long l,long long r,long long s){
	upd(k,x,y);
	if(y<l||x>r) return;
	long long mid=(x+y)/2;
	if(x>=l&&y<=r){ 
		ad[k<<1][0]+=s;ad[k<<1][1]=1;
		ad[k<<1|1][0]+=s;ad[k<<1|1][1]=1;
		dis[k]+=s;
		upd(k,x,y);
		return;
	}
	add(k<<1,x,mid,l,r,s);
	add(k<<1|1,mid+1,y,l,r,s);
	dis[k]=max(dis[k<<1],dis[k<<1|1]);
	upd(k,x,y);
	return;
}
long long find(long long k,long long x,long long y,long long l,long long r){
	upd(k,x,y);
	if(y<l||x>r) return -0x3f3f3f3f3f;
	long long mid=(x+y)/2;
	if(x>=l&&y<=r){
		return dis[k];
	}
	return max(find(k<<1|1,mid+1,y,l,r),find(k<<1,x,mid,l,r));
}
int main(){
	n=read();q=read();
	for(long long i=1;i<=n*4;i++) dis[i]=-0x3f3f3f3f3f;
	for(long long i=1;i<=n;i++){
		a=read();
		adb(1,1,n,a,i);
	}
	while(q--){
		long long op;
		op=read();
		long long l,r,x;
		if(op==1){
			l=read();r=read();x=read();
			if(l>r) swap(l,r);
			adm(1,1,n,l,r,x);
		}
		if(op==2){
			l=read();r=read();x=read();
			if(l>r) swap(l,r);
			add(1,1,n,l,r,x);
		}
		if(op==3){
			l=read();r=read();
			if(l>r) swap(l,r);
			printf("%lld\n",find(1,1,n,l,r));
		}
	}
	return 0;
}