萌新求调简单线段树,3 关注为报

P1253 扶苏的问题

lanretE @ 2022-08-24 13:00:28

rt,样例是过不了的。但是有 20pts。

求调

#include<iostream>
using namespace std;
const int N=1000010;
#define int long long
int n;
int a[N];
const int null=-19260817;
struct tree{
    int cover,add,maxx;
    #define cover(p) t[p].cover
    #define add(p) t[p].add
    #define maxx(p) t[p].maxx
}t[N<<2];
void pushup(int p){
    maxx(p)=max(maxx(p<<1),maxx(p<<1|1));
}
void cover_down(int p){
    if(cover(p)!=null){//可能出现全部变成0
        add(p<<1)=add(p<<1|1)=0;
        maxx(p<<1)=maxx(p<<1|1)=cover(p);
        cover(p<<1)=cover(p<<1|1)=cover(p);
        cover(p)=null;
    }
}
void add_down(int p){
    if(add(p)){
        cover_down(p);
        maxx(p<<1)+=add(p);
        maxx(p<<1|1)+=add(p);
        add(p<<1)+=add(p);
        add(p<<1|1)+=add(p);
        add(p)=0;
    }
}
void pushdown(int p){
    cover_down(p);
    add_down(p);
}
void build(int p,int l,int r){
    if(l==r){
        maxx(p)=a[l];
        cover(p)=null;
        add(p)=0;
        return ;
    }
    int mid=l+r>>1;
    build(n<<1,l,mid);
    build(n<<1|1,mid+1,r);
    pushup(p);
}
void change_add(int p,int l,int r,int ll,int rr,int k){
    if(ll<=l && r<=rr){
        cover_down(p);
        maxx(p)+=k;
        add(p)+=k;
        return ;
    }
    pushdown(p);
    int mid=l+r>>1;
    if(ll<=mid) change_add(p<<1,l,mid,ll,rr,k);
    if(rr>=mid+1) change_add(p<<1|1,mid+1,r,ll,rr,k);
    pushup(p);
}
void change_cover(int p,int l,int r,int ll,int rr,int k){
    if(ll<=l && r<=rr){
        add(p)=0;
        maxx(p)=k;
        cover(p)=k;
        return ;
    }
    pushdown(p);
    int mid=l+r>>1;
    if(ll<=mid) change_cover(p<<1,l,mid,ll,rr,k);
    if(rr>=mid+1) change_cover(p<<1|1,mid+1,r,ll,rr,k);
    pushup(p);
}
int query(int p,int l,int r,int ll,int rr){
    if(ll<=l && r<=rr){
        return maxx(p);
    }
    pushdown(p);
    int mid=l+r>>1;
    int res=-999999999;
    if(ll<=mid) res=max(res,query(p<<1,l,mid,ll,rr));
    if(rr>=mid+1) res=max(res,query(p<<1|1,mid+1,r,ll,rr));
    return res;
}
signed main(){
    cin>>n; 
    int q; cin>>q;
    for(int i=1;i<=n;++i) scanf("%lld",&a[i]);
    build(1,1,n);
    for(int i=1;i<=(n<<2);++i) cover(i)=null;
    while(q--){
        int opt,l,r; scanf("%lld%lld%lld",&opt,&l,&r);
        if(opt==1){
            int k; scanf("%lld",&k);
            change_cover(1,1,n,l,r,k);
        }
        if(opt==2){
            int k; scanf("%lld",&k);
            change_add(1,1,n,l,r,k);
        }
        if(opt==3){
            cout<<query(1,1,n,l,r)<<endl;
        }
    }
    return 0;
}

by lanretE @ 2022-08-24 13:39:26

解决了

build 写错了

此贴结


by Eason2009 @ 2022-08-24 15:11:21

卧槽你是什么卷王。


by fengjinyonghu @ 2022-08-24 15:11:22

卧槽你是什么卷王。


|