Oct0pus1 @ 2022-09-26 10:38:23
#include<cstdio>
#include<climits>
#include<algorithm>
using namespace std;
const int L=1e6+10;
typedef long long ll;
struct node{
int l,r;
ll m,lp,la;
}t[L<<2];
ll a[L];
int n,q;
inline int read(void){
int f=1,x=0;
char ch=getchar();
while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
return f*x;
}
inline void build(int i,int l,int r){
t[i].l=l;t[i].r=r;t[i].la=LLONG_MIN;
if(l==r){t[i].m=a[l];return ;}
int mid=l+r>>1;
build(i<<1,l,mid);
build(i<<1|1,mid+1,r);
t[i].m=max(t[i<<1].m,t[i<<1|1].m);
}
inline void pushplus(int i){
if(t[i].lp){
t[i<<1].m+=t[i].lp;
t[i<<1|1].l+=t[i].lp;
t[i<<1].lp+=t[i].lp;
t[i<<1|1].lp+=t[i].lp;
t[i].lp=0;
}
}
inline void pushass(int i){
if(t[i].la!=LLONG_MIN){
t[i<<1].m=t[i].la;
t[i<<1|1].m=t[i].la;
t[i<<1].lp=t[i<<1|1].lp=0;
t[i<<1].la=t[i].la;
t[i<<1|1].la=t[i].la;
t[i].la=LLONG_MIN;
}
}
inline void assign(int i,int l,int r,ll v){
if(t[i].l>=l && t[i].r<=r){
t[i].m=v;
t[i].la=v;
t[i].lp=0;
return ;
}
if(t[i].l>r || t[i].r<l)return ;
pushass(i);
pushplus(i);
assign(i<<1,l,r,v);
assign(i<<1|1,l,r,v);
t[i].m=max(t[i<<1].m,t[i<<1|1].m);
}
inline void add(int i,int l,int r,ll v){
if(t[i].l>=l && t[i].r<=r){
t[i].m+=v;
t[i].lp+=v;
return ;
}
if(t[i].l>r || t[i].r<l)return ;
pushass(i);
pushplus(i);
add(i<<1,l,r,v);
add(i<<1|1,l,r,v);
t[i].m=max(t[i<<1].m,t[i<<1|1].m);
}
inline ll query(int i,int l,int r){
if(t[i].l>=l && t[i].r<=r)return t[i].m;
if(t[i].l>r || t[i].r<l)return LLONG_MIN;
pushass(i);
pushplus(i);
return max(query(i<<1,l,r),query(i<<1|1,l,r));
}
int main(){
n=read();q=read();
for(register int i=1;i<=n;i++)a[i]=read();
build(1,1,n);
while(q--){
register int op=read(),l=read(),r=read();register ll x;
switch(op){
case 1:x=read();assign(1,l,r,x);break;
case 2:x=read();add(1,l,r,x);break;
case 3:printf("%lld\n",query(1,l,r));break;
}
}
return 0;
}