蒟蒻50pts线段树求调

50pts

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+7;
struct node{
    int lazy_add,lazy_change,max;
}t[N<<2];
int n,q,L,R,k[N],a,b;
inline int ls(int u){return u<<1;}
inline int rs(int u){return u<<1|1;}
inline bool inrange(int l,int r){return L<=l&&r<=R;}
inline void add_sum(int u){t[u].max=max(t[ls(u)].max,t[rs(u)].max);}
void build_tree(int u,int l,int r){
    t[u].lazy_change=1e9+1;
    if(l==r){
        t[u].max=k[l];
        return;
    }
    int m=l+r>>1;
    build_tree(ls(u),l,m);
    build_tree(rs(u),m+1,r);
    add_sum(u);
}
inline void f(int u,int l,int r,int _lazy,int _change){
    if(_change<=1e9){
        t[u].max=_change;
        t[u].lazy_change=_change;
        t[u].lazy_add=0;
    }
    else{
        t[u].max+=_lazy;
        t[u].lazy_add+=_lazy;
    }
}
inline void downdate(int u,int l,int r){
    int m=l+r>>1;
    f(ls(u),l,m,t[u].lazy_add,t[u].lazy_change);
    f(rs(u),m+1,r,t[u].lazy_add,t[u].lazy_change);
    t[u].lazy_add=0;
    t[u].lazy_change=1e9+1;
}
void add(int u,int l,int r){
    //printf("A:%d %d %d %d\n",u,l,r,t[u].max);
    if(inrange(l,r)){
        f(u,l,r,a,b);
        return;
    }
    downdate(u,l,r);
    int m=l+r>>1;
    if(L<=m) add(ls(u),l,m);
    if(R>m) add(rs(u),m+1,r);
    add_sum(u);
}
int query(int u,int l,int r){
    //printf("Q:%d %d %d %d\n",u,l,r,t[u].max);
    if(inrange(l,r)) return t[u].max;
    downdate(u,l,r);
    int m=l+r>>1;
    int tmp=-1e9-1;
    if(L<=m) tmp=max(tmp,query(ls(u),l,m));
    if(R>m) tmp=max(tmp,query(rs(u),m+1,r));
    return tmp;
}
int main(){
    scanf("%d%d",&n,&q);
    for(int i=1;i<=n;i++) scanf("%d",&k[i]);
    build_tree(1,1,n);
    while(q--){
        int opt;
        scanf("%d",&opt);
        if(opt==1){
            scanf("%d%d%d",&L,&R,&b);
            a=0;
            add(1,1,n);
        }
        if(opt==2){
            scanf("%d%d%d",&L,&R,&a);
            b=1e9+1;
            add(1,1,n);
        }
        if(opt==3){
            scanf("%d%d",&L,&R);
            printf("%d\n",query(1,1,n));
        }
    }
    return 0;
}