线段树20pts求调

rt

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
#define ls rt<<1
#define rs rt<<1|1
inline int rd(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while('0'<=ch&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*f;
}
const int N=1e6+7;
const int inf=1e18;
int n,q,a[N];
struct tree{
    int x,ldj,ldf;
}t[N<<2];

inline void pushup(int rt){
    t[rt].x=max(t[ls].x,t[rs].x);
}

inline void flazy(int rt,int l,int r,int F){
    t[rt].ldf=F;
    t[rt].ldj=0; 
    t[rt].x=F*(r-l+1);
    return; 
}

inline void addlazy(int rt,int l,int r,int C){
    t[rt].ldj+=C;
    t[rt].x+=C*(r-l+1);
    return; 
}

void pushdown(int rt,int l,int r){
    int mid=(l+r)>>1;
    if(t[rt].ldf!=inf){ 
        flazy(ls,l,mid,t[rt].ldf);
        flazy(rs,mid+1,r,t[rt].ldf);
        t[rt].ldf=inf; 
    }
    if(t[rt].ldj){
        addlazy(ls,l,mid,t[rt].ldj);
        addlazy(rs,mid+1,r,t[rt].ldj);
        t[rt].ldj=0;
    }   
    return;
}

void gz(int rt,int l,int r){
    t[rt].ldf=inf;
    t[rt].ldj=0;
    if(l==r){
        t[rt].x=a[l];
        return;
    }
    int mid=(l+r)>>1;
    gz(ls,l,mid);
    gz(rs,mid+1,r);
    pushup(rt);
}

void fz(int L,int R,int F,int l,int r,int rt){
    if(L<=l&&r<=R){
        flazy(rt,l,r,F);
        return;
    }
    pushdown(rt,l,r);
    int mid=(l+r)>>1;
    if(L<=mid)fz(L,R,F,l,mid,ls);
    if(R>mid)fz(L,R,F,mid+1,r,rs);
    pushup(rt);
}

void jz(int L,int R,int C,int l,int r,int rt){
    if(L<=l&&r<=R){
        addlazy(rt,l,r,C);
        return;
    }
    pushdown(rt,l,r);
    int mid=(l+r)>>1;
    if(L<=mid)jz(L,R,C,l,mid,ls);
    if(R>mid)jz(L,R,C,mid+1,r,rs);
    pushup(rt);
}

int query(int L,int R,int l,int r,int rt){
    if(L>r||R<l)return 0;
    if(L<=l&&r<=R)return t[rt].x;
    pushdown(rt,l,r);
    int mid=(l+r)>>1;
    return max(query(L,R,l,mid,ls),query(L,R,mid+1,r,rs));
}

signed main(){
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    gz(1,1,n);
    while(q--){
        int op,l,r,x;
        cin>>op>>l>>r;
        if(op==1){
            cin>>x;
            fz(l,r,x,1,n,1);
        }else if(op==2){
            cin>>x;
            jz(l,r,x,1,n,1);
        }else{
            cout<<query(l,r,1,n,1)<<"\n";
        }
    }
}