线段树萌新50分,秋眺QWQ

P1253 扶苏的问题

CMiBold @ 2024-11-20 23:38:12

调了1个小时没调出来,嘛回事啊,还是求各位大佬帮忙求调,谢谢了。

#include<bits/stdc++.h>
using namespace std;
#define luo_xing main
#define pb push_back
typedef long long ll;
const int N=1e6+10;
ll q,n,op;
ll f[N*4],tag[N*4],xiu[N*4]; 
ll xy[N*4];
void build(ll k,ll l,ll r){
    if(l==r){
        cin>>f[k];  
        return;
    }
    ll mid=(l+r)>>1;
    build(k*2,l,mid);
    build(k*2+1,mid+1,r);
    f[k]=max(f[k*2],f[k*2+1]);
    return;
}
void put_xiu(ll k){
    if(xy[k]){
        xiu[k*2]=xiu[k];
        xiu[k*2+1]=xiu[k];
        f[k*2]=xiu[k];
        f[k*2+1]=xiu[k];
        xy[k*2]=1;
        xy[k*2+1]=1;
        xy[k]=0;
        tag[k*2+1]=0;
        tag[k*2]=0;
    }
    return;
}
void put_tag(ll k){
//  cout<<"tag:"<<tag[k*2]<<" "<<tag[k*2+1]<<" "<<tag[k]<<" "<<k<<endl;
    tag[k*2]+=tag[k];
    tag[k*2+1]+=tag[k];
    f[k*2]+=tag[k];
    f[k*2+1]+=tag[k];
    tag[k]=0;
    return;
}
void xchange(ll k,ll l,ll r,ll x,ll y,ll v){
    if(l>y || r<x) return;
    if(l>=x && r<=y){
        f[k]=v;
        xy[k]=1;
        xiu[k]=v;
        tag[k]=0;
        return;
    }
    ll mid=(l+r)>>1;
    put_xiu(k);
    put_tag(k);
    xchange(k*2,l,mid,x,y,v);
    xchange(k*2+1,mid+1,r,x,y,v);
    f[k]=max(f[k*2],f[k*2+1]);
    return;
}
void jchange(ll k,ll l,ll r,ll x,ll y,ll v){
    if(l>y || r<x) return;
    if(l>=x && r<=y){
        if(xy[k]) xiu[k]+=v;
        f[k]+=v;
        tag[k]+=v;
        return;
    }
    ll mid=(l+r)>>1;
    put_xiu(k);
    put_tag(k);
    jchange(k*2,l,mid,x,y,v);
    jchange(k*2+1,mid+1,r,x,y,v);
    f[k]=max(f[k*2],f[k*2+1]);
    return;
}
ll ask(ll k,ll l,ll r,ll x,ll y){
    if(l>y || r<x) return -INT_MAX;
    if(l>=x && r<=y){
        if(xy[k]) return xiu[k];
        return f[k];
    }
    ll mid=(l+r)>>1;
    put_xiu(k);
    put_tag(k);
    ll ma=0;
    ma=max(ask(k*2,l,mid,x,y),ask(k*2+1,mid+1,r,x,y));
    return ma;
}
int luo_xing(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin>>n>>q;
    build(1,1,n);
    ll l,r,x;
    while(q--){
        cin>>op>>l>>r;
        if(op==1){
            cin>>x;
            xchange(1,1,n,l,r,x);
        }else if(op==2){
            cin>>x;
            jchange(1,1,n,l,r,x);
        }else{
            cout<<ask(1,1,n,l,r)<<'\n';
        }
    }
    return 0;
}

QWQ


by xlpri @ 2024-11-21 01:35:27

码风过于独特了


by xlpri @ 2024-11-21 02:07:11

代码有点太抽象了,你出错的地方大概是xy数组没有更新导致的

(没猜错的话f数组是以对应序列中最大值为中间节点的线段树,xiu数组是加法懒标记,tag是更改数字懒标记)


by xlpri @ 2024-11-21 02:10:26

还有建议把P3372和3373弄熟练了,而不是AC就行


by CMiBold @ 2024-11-21 21:44:25

@xlpri ok,谢谢大佬


|