WA后四个点
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define N 1000100
void read(int &x){
x=0;
long long f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<3)+(x<<1)+ch-48;
ch=getchar();
}
x*=f;
}
int n,m,opt,x,y,k;
int a[N];
struct node{
int l,r,mx,lz,add;
}tree[N*4];
void pushdown(int u){
if(tree[u].lz==-1e18){
tree[u*2].add+=tree[u].add;
tree[u*2+1].add+=tree[u].add;
tree[u*2].mx+=tree[u].add;
tree[u*2+1].mx+=tree[u].add;
tree[u].add=0;
}
else{
tree[u*2].lz=tree[u].lz;
tree[u*2+1].lz=tree[u].lz;
tree[u*2].mx=tree[u].lz;
tree[u*2+1].mx=tree[u].lz;
tree[u].lz=-1e18;
}
}
void build(int u,int l,int r){
tree[u].l=l;
tree[u].r=r;
tree[u].lz=-1e18;
if(l==r){
tree[u].mx=a[l];
return ;
}
int mid=(l+r)>>1;
if(l<=mid) build(u*2,l,mid);
if(r>mid) build(u*2+1,mid+1,r);
tree[u].mx=max(tree[u*2].mx,tree[u*2+1].mx);
}
void update(int u,int l,int r,int x){
if(l<=tree[u].l&&tree[u].r<=r){
tree[u].mx=x;
tree[u].lz=x;
tree[u].add=0;
return ;
}
pushdown(u);
int mid=(tree[u].l+tree[u].r)>>1;
if(l<=mid) update(u*2,l,r,x);
if(r>mid) update(u*2+1,l,r,x);
tree[u].mx=max(tree[u*2].mx,tree[u*2+1].mx);
}
void update1(int u,int l,int r,int x){
if(l<=tree[u].l&&tree[u].r<=r){
if(tree[u].lz!=-1e18) tree[u].lz+=x;
else tree[u].add+=x;
tree[u].mx+=x;
return ;
}
pushdown(u);
int mid=(tree[u].l+tree[u].r)>>1;
if(l<=mid) update1(u*2,l,r,x);
if(r>mid) update1(u*2+1,l,r,x);
tree[u].mx=max(tree[u*2].mx,tree[u*2+1].mx);
}
int query(int u,int l,int r){
if(l<=tree[u].l&&tree[u].r<=r){
return tree[u].mx;
}
pushdown(u);
int mid=(tree[u].l+tree[u].r)>>1;
int ans=-1e18;
if(l<=mid) ans=max(ans,query(u*2,l,r));
if(r>mid) ans=max(ans,query(u*2+1,l,r));
return ans;
}
signed main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
read(n);read(m);
for(int i=1;i<=n;i++) read(a[i]);
build(1,1,n);
while(m--){
read(opt);read(x);read(y);
if(opt==1){
read(k);
update(1,x,y,k);
}
else if(opt==2){
read(k);
update1(1,x,y,k);
}
else{
cout<<query(1,x,y)<<"\n";
}
}
return 0;
}