qqq100 @ 2023-10-14 15:38:14
#include <bits/stdc++.h>
using namespace std;
int a[1000010];
struct node{
int l,r,add,dal,mx; //dal记录延迟修改
//add记录延迟增加
//mx记录区间最大值
node* lch;node* rch;
node(){
l=r=add=dal=mx=-INT_MAX;
lch=rch=NULL;
}
};
void build(node* root,int l,int r){
root->l=l;root->r=r;
if(l+1<r){
root->lch=new(node);
root->rch=new(node);
build(root->lch,l,(l+r)>>1);
build(root->rch,(l+r)>>1+1,r);
root->mx=max(root->lch->mx,root->rch->mx);
}else{
root->lch=root->rch=NULL;
root->mx=a[l];
}
}
void updal(node* root){
root->mx=root->dal;
if(root->lch!=NULL) root->lch->dal=root->dal;
if(root->rch!=NULL) root->rch->dal=root->dal;
root->dal=-INT_MAX;
}
void upadd(node* root){
root->mx+=root->add;
if(root->lch!=NULL)root->lch->add=root->add;
if(root->rch!=NULL) root->rch->add=root->add;
root->add=-INT_MAX;
}
void ame(node* root,int l,int r,int x){
if(root->dal!=-INT_MAX) updal(root);
if(root->lch==NULL||root->rch==NULL) return ;
if(l<=root->l&&r>=root->r){
root->mx=x;root->lch->dal=root->rch->dal=x;
}else{
if(l<(root->l+root->r)/2)
ame(root->lch,l,r,x);
if(r>(root->l+root->r)/2)
ame(root->rch,l,r,x);
}
}
void add(node* root,int l,int r,int x){
if(root->add!=-INT_MAX) upadd(root);
if(root->lch==NULL||root->rch==NULL) return ;
if(l<=root->l&&r>=root->r){
root->mx+=x;root->lch->add=root->rch->add=x;
}else{
if(l<(root->l+root->r)/2)
add(root->lch,l,r,x);
if(r>(root->l+root->r)/2)
add(root->rch,l,r,x);
}
}
int find_max(node* root,int l,int r){
if(root->add!=-INT_MAX) upadd(root);
if(root->dal!=-INT_MAX) updal(root);
if(root->lch==NULL||root->rch==NULL)
return root->mx;
int ans=-INT_MAX;
if(l<=root->l&&r>=root->r)
ans=max(ans,root->mx);
if(l<(root->l+root->r)/2)
ans=max(ans,find_max(root->lch,l,r));
if(r>(root->l+root->r)/2)
ans=max(ans,find_max(root->rch,l,r));
return ans;
}
int n,q,op,l,r,x;
int main(){
scanf("%d %d",&n,&q);
node* root=new(node);
for(int i=1;i<=n;i++) scanf("%d",a+i);
build(root,1,n);
while(q--){
scanf("%d %d %d",&op,&l,&r);
switch(op){
case 1:
scanf("%d",&x);
ame(root,l,r,x);
break;
case 2:
scanf("%d",&x);
add(root,l,r,x);
break;
case 3:
printf("%d\n",find_max(root,l,r));
break;
}
}
return 0;
}