结构体线段树60Pts求调,WA on #7~#10

P1253 扶苏的问题

Reaper_Osiris @ 2023-07-15 12:00:01

#include<bits/stdc++.h>
#define elif else if
using namespace std;
typedef long long ll;
const ll N=1e6+5;
const ll ll_max=9223372036854775783;//long long 范围内最大的质数 
ll a[N],n,ln,rn,sum,q,opt;
//原数组a,长度n,操作区间[ln,rn],操作数sum,命令opt 
struct LineTree_max{//最大值线段树 
    ll l[N<<2],r[N<<2],v[N<<2],ta_add[N<<2],ta_cov[N<<2];
//左右儿子l,r,最大值v,加tag ta_add,赋值tag ta_cov 
    inline void pdc(ll p){//pushdown_cover
        if(ta_cov[p]==ll_max)return;
        ll pl=p<<1,pr=p<<1|1;//左右儿子 
        v[pl]=v[pr]=ta_cov[p];
        ta_cov[pr]=ta_cov[pl]=ta_cov[p];
        ta_cov[p]=ll_max;
        ta_add[p]=ta_add[pl]=ta_add[pr]=0;
    }
    inline void pda(ll p){//pushdown_add
        if(!ta_add[p])return;
        ll pl=p<<1,pr=p<<1|1;//左右儿子 
        v[pl]+=ta_add[p];
        ta_add[pl]+=ta_add[p];
        v[pr]+=ta_add[p];
        ta_add[pr]+=ta_add[p];
        ta_add[p]=0;
    }
    //不想动脑子,就把cover和add的pushdown分开写了 
    inline ll bu(ll p,ll lu,ll ru){//build
        l[p]=lu,r[p]=ru,ta_cov[p]=ll_max;
        if(lu==ru)return v[p]=a[lu];
        ll mid=(lu+ru)>>1;
        return v[p]=max(bu(p<<1,lu,mid),bu(p<<1|1,mid+1,ru));
    }
    inline ll gs(ll p){//getsum
        if(ln>r[p]||rn<l[p])return -ll_max;//防止负值出错 
        if(ln<=l[p]&&r[p]<=rn) return v[p];//在区间内 
        pdc(p);
        pda(p);//先cover再add 
        return max(gs(p<<1),gs(p<<1|1));
    }
    inline void uc(ll p){//update_cover
        if(ln<=l[p]&&r[p]<=rn){//在区间内
            v[p]=sum;
            ta_cov[p]=sum;
            ta_add[p]=0;
            return;
        }
        pdc(p);
        ll pl=p<<1,pr=p<<1|1;
        if(ln<=r[pl])uc(pl);
        if(rn>=l[pr])uc(pr);
        v[p]=max(v[pl],v[pr]);
    }
    inline void ua(ll p){//update_add
        pdc(p);
        if(ln<=l[p]&&r[p]<=rn){//在区间内
            v[p]+=sum;
            ta_add[p]+=sum;
            return;
        }
        pda(p);
        ll pl=p<<1,pr=p<<1|1;
        if(ln<=r[pl])ua(pl);
        if(rn>=l[pr])ua(pr);
        v[p]=max(v[pl],v[pr]);
    }
}LT;
int main(){
    //freopen("P1253_7.in","r",stdin);
    //freopen("P1253_7.ans","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>q;
    for(int i=1;i<=n;i++)cin>>a[i];
    LT.bu(1,1,n);
    for(int i=1;i<=q;i++){
        cin>>opt>>ln>>rn;
        if(opt==1){
            cin>>sum;
            LT.uc(1);
        }
        elif(opt==2){
            cin>>sum;
            LT.ua(1);
        }
        elif(opt==3) cout<<LT.gs(1)<<'\n';
    }
    return 0;
}

调了一个上午,从20分调到60分,人都调麻了。
求各位dalao帮忙调调。


by Epoch_L @ 2023-07-15 13:00:16


by Reaper_Osiris @ 2023-07-15 17:04:10

屮,蒟蒻一直以为cover覆盖了add就没用了。 原来不能直接覆盖


by Reaper_Osiris @ 2023-07-15 17:06:37

只剩#10还没过了,谢谢佬
@Epoch_L


by Reaper_Osiris @ 2023-07-15 17:14:52

8倍数组过了?!
此贴结。


|