50分求救!

P1253 扶苏的问题

liu_ruoyu @ 2024-01-30 11:27:06


#include<iostream>
using namespace std;
#define lson(x) x*2
#define rson(x) x*2+1
#define int long long
const int MAXN=1e6+10;
int n,q;
int a[MAXN],st[MAXN*4],delay[MAXN*4],g[4*MAXN];
void push_up(int t){
    st[t]=max(st[lson(t)],st[rson(t)]);
}
void build(int t,int l,int r){
    g[t]=1e18;
    if(l==r){
        st[t]=a[l];
    }
    if(r>l){
        int mid=(l+r)/2;
        build(lson(t),l,mid);
        build(rson(t),mid+1,r);
        push_up(t);
    }
}

void push_down(int t,int l,int r){
//  cout<<2;
    if(!delay[t])
        return ;
    delay[lson(t)]+=delay[t];
    delay[rson(t)]+=delay[t];
    st[lson(t)]+=delay[t];
    st[rson(t)]+=delay[t];
    delay[t]=0;
}
void gai(int t, int l, int r)
{
    if(g[t] == 1e18)
        return ;
    st[t] = g[t];
    g[lson(t)] = g[t];
    g[rson(t)] = g[t];
    g[t] = 1e18;
    delay[lson(t)]=0;
    delay[rson(t)]=0;
}
// 2 2 3 4 5
void up_date(int t,int l,int r,int x,int y,int v,int op){
//    cout<<1<<"\n";
    if(l>=x&&r<=y){
        if(op == 1){
            st[t] = v;
            g[t] = v;
            delay[t]=0;
        }
        else{
            st[t]+=v;
            delay[t]+=v;
        }
        return ;
    }
    gai(t,l,r);
    push_down(t,l,r);
    int mid=l+(r-l)/2;
    if(x<=mid){
        up_date(lson(t),l,mid,x,y,v,op);
    }if(y>mid){
        up_date(rson(t),mid+1,r,x,y,v,op);
    }
    push_up(t);
}
int query(int t,int l,int r,int x,int y){
    if(l>=x&&r<=y){
        return st[t];
    }
    int mid=l+(r-l)/2;
    gai(t,l,r);
    push_down(t,l,r);
    int ans=-1e18;
    if(x<=mid){
        ans=max(ans,query(lson(t),l,mid,x,y));
    }
    if(y>mid){
        ans=max(ans,query(rson(t),mid+1,r,x,y));
    }
    return ans;
}
signed main(){
    ios::sync_with_stdio(false);
    std::cin.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>a[i];
    }
    build(1,1,n);
    while(q--){
        int point;
        int l,r,x;
        cin>>point>>l>>r;
        if(point==1){
            cin>>x;
            up_date(1,1,n,l,r,x,point);
        }else if(point==2){
            cin>>x;
            up_date(1,1,n,l,r,x,point);
        }else if(point==3){
            cout<<query(1,1,n,l,r)<<"\n";
        }
    }
    return 0;
}
// 6 6
// 1 1 4 5 1 4
// 1 1 2 6
// 2 3 4 2
// 3 1 4
// 3 2 3
// 1 1 6 -1
// 3 1 6

by clx201022 @ 2024-01-30 11:40:11

@liu_ruoyu long long


by shixuanzhe_ha @ 2024-01-30 11:43:56

@liu_ruoyu 线下帮你改 AC 了……


by shixuanzhe_ha @ 2024-01-30 11:45:01

@liu_ruoyu 覆盖修改时要把左右子树也修改了


by liu_ruoyu @ 2024-01-30 11:48:30

@shixuanzhe_ha 谢谢


|