萌新刚学线段树 60pts 求调

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=1e6+5;
ll sum[N<<2],lazy[N<<2],change[N<<2],a[N];
bitset <N<<2>vis;

void Pushup(ll rt){
    sum[rt]=max(sum[rt<<1],sum[rt<<1|1]);
}

void build(ll s,ll t,ll rt){
    if(s==t){
        sum[rt]=a[s];
        return ;
    }
    ll mid=s+t>>1;
    build(s,mid,rt<<1);
    build(mid+1,t,rt<<1|1);
    Pushup(rt);
}

void Pushdown(ll s,ll t,ll rt){
    if(vis[rt]){
        lazy[rt]=0;
        sum[rt<<1]=change[rt];
        sum[rt<<1|1]=change[rt];
        change[rt<<1]=change[rt];
        change[rt<<1|1]=change[rt];
        vis[rt<<1]=1;
        vis[rt<<1|1]=1;
        vis[rt]=0;
    }
    else if(lazy[rt]){
        if(change[rt<<1]) change[rt<<1]+=lazy[rt];
        if(change[rt<<1|1]) change[rt<<1|1]+=lazy[rt];
        sum[rt<<1]+=lazy[rt];
        sum[rt<<1|1]+=lazy[rt];
        lazy[rt<<1]+=lazy[rt];
        lazy[rt<<1|1]+=lazy[rt];
        lazy[rt]=0;
    }
}

void updata(ll s,ll t,ll l,ll r,ll rt,ll x){
    if(l<=s&&t<=r){
        sum[rt]+=x;
        lazy[rt]+=x;
        return;
    }
    Pushdown(s,t,rt);
    ll mid=s+t>>1;
    if(l<=mid) updata(s,mid,l,r,rt<<1,x);
    if(mid<r) updata(mid+1,t,l,r,rt<<1|1,x);
    Pushup(rt);
}

void opdate(ll s,ll t,ll l,ll r,ll rt,ll x){
    if(l<=s&&t<=r){
        sum[rt]=x;
        change[rt]=x;
        vis[rt]=1;
        return ;
    }
    Pushdown(s,t,rt);
    ll mid=s+t>>1;
    if(l<=mid) opdate(s,mid,l,r,rt<<1,x);
    if(mid<r) opdate(mid+1,t,l,r,rt<<1|1,x);
    Pushup(rt);
}

ll Query(ll s,ll t,ll l,ll r,ll rt){
    if(l<=s&&t<=r)
        return sum[rt];     
    Pushdown(s,t,rt);
    ll mid=s+t>>1;
    ll ans=-1e18;
    if(l<=mid) ans=max(ans,Query(s,mid,l,r,rt<<1));
    if(mid<r) ans=max(ans,Query(mid+1,t,l,r,rt<<1|1));
    return ans;
}

signed main(){
    ll n,q;
    scanf("%lld %lld",&n,&q);
    for(ll i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    build(1,n,1);
    for(ll i=1;i<=q;i++){
        ll op;
        scanf("%lld",&op);
        if(op==1){
            ll l,r,x;
            scanf("%lld %lld %lld",&l,&r,&x);
            opdate(1,n,l,r,1,x);
        }
        else if(op==2){
            ll l,r,x;
            scanf("%lld %lld %lld",&l,&r,&x);
            updata(1,n,l,r,1,x);
        }
        else {
            ll l,r;
            scanf("%lld %lld",&l,&r);
            printf("%lld\n",Query(1,n,l,r,1));
        }
    }
    return 0;
}

https://www.luogu.com.cn/record/121484694