60pts 求助

P1253 扶苏的问题

_QyGyQ_ @ 2024-01-16 14:06:10

#include<bits/stdc++.h>
#define int long long
#define lc(p) (p<<1)
#define rc(p) (p<<1|1)
using namespace std;
using ll=long long;
const int N=1e6+7;
const int INF=1e11;
int tag_add[N<<2];
int tag_ch[N<<2];
int tree[N<<2];
int a[N];
int n,m;
void push_up(int p){
    tree[p]=max(tree[lc(p)],tree[rc(p)]);
}
void build(int p,int pl,int pr){
    if(pl==pr){
        tree[p]=a[pl];
        return ;
    }
    int mid=pl+pr>>1;
    build(lc(p),pl,mid);
    build(rc(p),mid+1,pr);
    push_up(p);
}
void add_tag_add(int p,int pl,int pr,int d){
    tree[p]+=d;
    tag_add[p]+=d;
    if(tag_ch[p]!=INF) tag_ch[p]+=d;
}
void add_tag_ch(int p,int pl,int pr,int d){
    tree[p]=d;
    tag_ch[p]=d;
    tag_add[p]=0;
}
void push_down(int p,int pl,int pr){
    int mid=pl+pr>>1;
    if(tag_ch[p]!=INF){
        add_tag_ch(lc(p),pl,mid,tag_ch[p]);
        add_tag_ch(rc(p),mid+1,pr,tag_ch[p]);
        tag_ch[p]=INF;
    }
    if(tag_add[p]){
        add_tag_add(lc(p),pl,mid,tag_add[p]);
        add_tag_add(rc(p),mid+1,pr,tag_add[p]);
        tag_add[p]=0;
    }
}
void update_change(int L,int R,int p,int pl,int pr,int d){
    if(L<=pl&&pr<=R){
        add_tag_ch(p,pl,pr,d);
        return ;
    }
    push_down(p,pl,pr);
    int mid=pl+pr>>1;
    if(L<=mid) update_change(L,R,lc(p),pl,mid,d);
    if(R>mid) update_change(L,R,rc(p),mid+1,pr,d);
    push_up(p);
}
void update_add(int L,int R,int p,int pl,int pr,int d){
    if(L<=pl&&pr<=R){
        add_tag_add(p,pl,pr,d);
        return ;
    }
    push_down(p,pl,pr);
    int mid=pl+pr>>1;
    if(L<=mid) update_add(L,R,lc(p),pl,mid,d);
    if(R>mid) update_add(L,R,rc(p),mid+1,pr,d);
    push_up(p);
}
int query(int L,int R,int p,int pl,int pr){
    if(L<=pl&&pr<=R){
        return tree[p];
    }
    push_down(p,pl,pr);
    int res=-2147483647000;
    int mid=pl+pr>>1;
    if(L<=mid) res=max(res,query(L,R,lc(p),pl,mid));
    if(R>mid) res=max(res,query(L,R,rc(p),mid+1,pr));
    return res;
}
void put(){
    for(int i=1;i<=n;i++){
        cout<<query(i,i,1,1,n)<<" ";
    }
    puts("---------debug----------");
}
signed main(){
    for(int i=1;i<=(N<<2);i++){
        tag_ch[i]=INF;
    }
    int q;
    scanf("%lld%lld",&n,&q);
    for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
    build(1,1,n);
    while(q--){
        int op,l,r;
        scanf("%lld%lld%lld",&op,&l,&r);
        if(op==1){
            int x;
            scanf("%lld",&x);
            update_change(l,r,1,1,n,x);
        }
        else if(op==2){
            int x;
            scanf("%lld",&x);
            update_add(l,r,1,1,n,x);
        }
        else{
            printf("%lld\n",query(l,r,1,1,n));
        }
        //put();
    }
    return 0;
}

by 杜都督 @ 2024-01-30 05:07:33

把第29行tag_add[p]+=d;放到后面的if的else里就可以100分了

因为如果ch标记存在,那么应该仅修改ch,不存在时才修改add,而不是无论如何都修改add

根据逻辑很容易就能推断出ch和add两个标记不可能同时存在,如果按照你原先的写法,push_down()中的ch和add两个操作可能都会执行,从而导致数据出错


|