mxjz666 @ 2024-03-31 21:43:14
#include<bits/stdc++.h>
using namespace std;
#define int long long
int n,q;
const int N=1e5+10;
int a[4*N];
struct info{
int maxv;
};
struct tr{
int add;
};
info operator + (const info &x,const info &y){
info cnt={max(x.maxv,y.maxv)};
return cnt;
}
info operator + (const info &x,const tr &add){
info cnt={x.maxv+add.add};
return cnt;
}
tr operator + (const tr &x,const tr &y){
tr cnt={x.add+y.add};
return cnt;
}
struct node{
tr t;
info v;
}tree[4*N];
void update(int id){
tree[id].v=tree[id*2].v+tree[id*2+1].v;
return;
}
void tadd(int id,tr x){
tree[id].v=tree[id].v+x;
tree[id].t=tree[id].t+x;
return;
}
void down(int id){
if(tree[id].t.add!=0){
tadd(id*2,tree[id].t);
tadd(id*2+1,tree[id].t);
tree[id].t.add=0;
}
return;
}
void build(int id,int l,int r){
if(l==r){
tree[id].v={a[l]};
}else{
int mid=(l+r)/2;
build(id*2,l,mid);
build(id*2+1,mid+1,r);
update(id);
}
return;
}
void work(int id,int l,int r,int ql,int qr,tr val){
if(l==r){
tadd(id,val);
return;
}
int mid=(l+r)/2;
down(id);
if(qr<=mid){
work(id*2,l,mid,ql,qr,val);
}else if(ql>mid){
work(id*2+1,mid+1,r,ql,qr,val);
}else{
work(id*2,l,mid,ql,mid,val);
work(id*2+1,mid+1,r,mid+1,qr,val);
}
update(id);
return;
}
info qu(int id,int l,int r,int ql,int qr){
if(l==ql&&r==qr){
return tree[id].v;
}
int mid=(l+r)/2;
down(id);
if(qr<=mid){
return qu(id*2,l,mid,ql,qr);
}else if(ql>mid){
return qu(id*2+1,mid+1,r,ql,qr);
}else{
return qu(id*2,l,mid,ql,mid)+qu(id*2+1,mid+1,r,mid+1,qr);
}
}
signed main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++){
cin>>a[i];
}
build(1,1,n);
while(m--){
int x;
cin>>x;
if(x==1){
int y,z,k;
cin>>y>>z>>k;
work(1,1,n,y,z,{k});
}else{
int y,z;
cin>>y>>z;
auto ans=qu(1,1,n,y,z);
cout<<ans.maxv<<endl;
}
}
return 0;
}