tyz090617 @ 2024-08-07 22:34:06
#include<bits/stdc++.h>
#include<vector>
#include<map>
#define int long long
#define maxn 1e18
using namespace std;
void build_sg(int q,int l,int r);
inline void lazy_up_sg(int q);
void revinter_sg(int q,int x,int y,int z);
int findp_sg(int q,int x);
inline void lazy_down_sg(int q);
int findmax_sg(int q,int x,int y);
void revinterv_sg(int q,int x,int y,int z);
struct segment_tree{
int l,r;
int mv;
}segtree[10000005];
inline int read(){
int x=0,f=1;
char c=getchar();
while(c<'0'||c>'9'){
if(c=='-')f=-1;
c=getchar();
}
while(c>='0'&&c<='9'){
x=x*10+c-'0';
c=getchar();
}return x*f;
}
int treesize,tz,fr[10000005],siz,tag[10000005]={},tagv[1000005];
bool kk[10000005];
int a,b,c,d,e,f,g;
signed main(){
cin>>a>>b;
for(int i=1;i<=a;i++){
fr[i]=read();
}treesize=tz=2*a-1;siz=a;
build_sg(1,1,siz);
for(int i=1;i<=b;i++){
c=read();
if(c==2){
d=read();e=read();f=read();
revinter_sg(1,d,e,f);
// errtr_sg();
}else if(c==1){
d=read();e=read();f=read();
revinterv_sg(1,d,e,f);//errtr_sg();
}else{
d=read();e=read();
cout<<findmax_sg(1,d,e)<<endl;
}
}
return 0;
}
void revinterv_sg(int q,int x,int y,int z){
if(x<=segtree[q].l&&segtree[q].r<=y) {
if(tag[q])lazy_down_sg(q);
segtree[q].mv=z;
tagv[q]=z;
tag[q]=0;
kk[q]=1;
return ;
}
lazy_down_sg(q);
int mid=(segtree[q].l+segtree[q].r)>>1,u=q<<1;
if(x<=mid)revinterv_sg(u,x,y,z);
if(y>mid)revinterv_sg(u+1,x,y,z);
lazy_up_sg(q);
}
void revinter_sg(int q,int x,int y,int z){
if(x<=segtree[q].l&&segtree[q].r<=y) {
if(kk[q])lazy_down_sg(q);
segtree[q].mv+=z;
tag[q]+=z;
return ;
}
lazy_down_sg(q);
int mid=(segtree[q].l+segtree[q].r)>>1,u=q<<1;
if(x<=mid)revinter_sg(u,x,y,z);
if(y>mid)revinter_sg(u+1,x,y,z);
lazy_up_sg(q);
}
int findmax_sg(int q,int x,int y){
if(x<=segtree[q].l&&segtree[q].r<=y) {
return segtree[q].mv;
}
lazy_down_sg(q);
int mid=(segtree[q].l+segtree[q].r)>>1,u=q<<1,ans=-maxn;
if(x<=mid)ans=max(findmax_sg(u,x,y),ans);
if(y>mid)ans=max(findmax_sg(u+1,x,y),ans);
lazy_up_sg(q);
return ans;
}
void lazy_down_sg(int q){
if(kk[q]){
int u=q<<1,l=segtree[q].l,r=segtree[q].r;
int mid=(l+r)>>1;
tagv[u]=tagv[q];
tagv[u+1]=tagv[q];
kk[u]=1;
kk[u+1]=1;
segtree[u].mv=tagv[q];
segtree[u+1].mv=tagv[q];
//tagv_check(q,u);
tagv[q]=0;
kk[q]=0;
}
if(tag[q]){
int u=q<<1,l=segtree[q].l,r=segtree[q].r;
int mid=(l+r)>>1;
tag[u]+=tag[q];
tag[u+1]+=tag[q];
segtree[u].mv+=tag[q];
segtree[u+1].mv+=tag[q];
tag[q]=0;
}
}
void lazy_up_sg(int q){
int u=q<<1;
segtree[q].mv=max(segtree[u].mv,segtree[u+1].mv);
}
void build_sg(int q,int l,int r){
segtree[q].l=l;segtree[q].r=r;
if(l==r){
segtree[q].mv=fr[l];
return ;
}int mid=(l+r)>>1,u=q<<1;
build_sg(u,l,mid);
build_sg(u+1,mid+1,r);
lazy_up_sg(q);
}