RT

Code:

#include<bits/stdc++.h>
using namespace std;
const int N=2e6+1;
int n,m,op;
int l,r,x;
typedef long long ll;
struct node{
	int l,r;
	ll w,add,ch;
}tr[4*N];
int a[N];
inline int read()
{
	int x=0,f=1;
	char ch;
	ch=getchar();
	while(ch>'9'||ch<'0')
	{
		if(ch=='-') f=-1;
		ch=getchar();
	}
	while(ch<='9'&&ch>='0') x=x*10+ch-'0',ch=getchar();
	return x*f;
}
inline void write(ll x)
{
	if(x<0) x=-x,putchar('-');
	if(x>9) write(x/10);
	putchar(x%10+'0');
}
void pushup(int u)
{
	tr[u].w=max(tr[u<<1].w,tr[u<<1|1].w);
}
void pushdown_c(int u)
{
	if(tr[u].ch!=-2e10)
	{
		tr[u<<1].add=0;
		tr[u<<1|1].add=0;
		tr[u<<1].w=tr[u<<1|1].w=tr[u].ch;
		tr[u<<1|1].ch=tr[u<<1].ch=tr[u].ch;
		tr[u].ch=-2e10;
	}	
}
void pushdown_j(int u)
{
	if(tr[u].add)
	{
		tr[u<<1].add+=tr[u].add;
		tr[u<<1].w+=tr[u].add;
		tr[u<<1|1].add+=tr[u].add;
		tr[u<<1|1].w+=tr[u].add;
		tr[u].add=0;
	}
}

void build(int u,int l,int r)
{
	tr[u].l=l,tr[u].r=r,tr[u].ch=-2e10;
	if(l==r)
	{
		tr[u].w=a[l];
		return;
	}
	int mid=l+r>>1;
	build(u<<1,l,mid);
	build(u<<1|1,mid+1,r);
	pushup(u);
}
void change(int u,int l,int r,int x)
{
	if(l<=tr[u].l&&r>=tr[u].r)
	{
		tr[u].add=0;
		tr[u].w=x;
		tr[u].ch=x;
		return;
	}
	pushdown_c(u);
	pushdown_j(u);
	int mid=tr[u].l+tr[u].r>>1;
	if(l<=mid) change(u<<1,l,r,x);
	if(r>mid) change(u<<1|1,l,r,x);
	pushup(u);
}
void jia(int u,int l,int r,int x)
{
	if(l<=tr[u].l&&r>=tr[u].r)
	{
		pushdown_c(u);
		tr[u].add+=x;
		tr[u].w+=x;
		return;
	}
	pushdown_c(u);
	pushdown_j(u);
	int mid=tr[u].l+tr[u].r>>1;
	if(l<=mid) jia(u<<1,l,r,x);
	if(r>mid) jia(u<<1|1,l,r,x);
	pushup(u);
}
ll query(int u,int l,int r)
{
	if(l<=tr[u].l&&r>=tr[u].r) return tr[u].w;
	pushdown_c(u);
	pushdown_j(u);
	int mid=tr[u].l+tr[u].r>>1;
	ll w=-2e10;
	if(l<=mid) w=query(u<<1,l,r);
	if(r>mid) w=max(w,query(u<<1|1,l,r));
	return w;
}
int main()
{
	n=read(),m=read();
	for(int i=1;i<=n;i++) a[i]=read();
	build(1,1,n);
	for(int i=1;i<=m;i++)
	{
		op=read();
		if(op!=3) l=read(),r=read(),x=read();
		else l=read(),r=read();
		if(op==1) change(1,l,r,x);
		else if(op==2) jia(1,l,r,x);
		else write(query(1,l,r)),putchar('\n');
	}
	return 0;
}