以AC,但是玄学问题,玄 1 关
查看原帖
以AC,但是玄学问题,玄 1 关
764773
AstaSunch_楼主2025/2/8 17:29

rt,这是我的代码:

#include<bits/stdc++.h>
#define LS tree[tree[rt].ls]
#define RS tree[tree[rt].rs]
using namespace std;
typedef long long ll;
const int MAXN=4e5+5;
struct node {
    ll vl,ky,sz,ls,rs,lzy,sum;
}tree[MAXN*40];
ll tot,roots[MAXN*40],ver,n;
long long lstans=0;
void pushup(ll rt) {
    tree[rt].sz=LS.sz+RS.sz+1;
    tree[rt].sum=LS.sum+RS.sum+tree[rt].vl;
}
void pushdown(ll rt) {
    if (!tree[rt].lzy) return;
    if (tree[rt].ls) {
        tree[++tot]=LS;
        tree[rt].ls=tot;
        LS.lzy^=1;
        swap(LS.ls,LS.rs);
    }
    if (tree[rt].rs) {
        tree[++tot]=RS;
        tree[rt].rs=tot;
        RS.lzy^=1;
        swap(RS.ls,RS.rs);
    }
    tree[rt].lzy=0;
}
void split(ll rt,ll k,ll &x,ll &y) {
    if (!rt) {x=y=0; return;}
    pushdown(rt);
    if (LS.sz>=k) {
    	y=++tot;
        tree[y]=tree[rt];
        split(tree[rt].ls,k,x,tree[y].ls);
        pushup(y);
    } else {
    	x=++tot;
        tree[x]=tree[rt];
        split(tree[rt].rs,k-LS.sz-1,tree[x].rs,y);
        pushup(x);
    }
}
ll merge(ll x,ll y) {
    if (!x||!y) return x+y;
    int u=++tot;
    if (tree[x].ky>tree[y].ky) {
        pushdown(x);
        tree[u]=tree[x];
        tree[u].rs=merge(tree[x].rs,y);
        
    } else {
        pushdown(y);
        tree[u]=tree[y];
        tree[u].ls=merge(x,tree[y].ls);
    }
    pushup(u);
    return u;
}
ll insert(ll val) {
    tree[++tot]={val,rand(),1,0,0,0,val};
    return tot;
}
long long query_sum(ll rt,ll l,ll r) {
    ll x,y,z;
    split(rt,r,x,z);
    split(x,l-1,x,y);
    long long ans=tree[y].sum;
    rt=merge(merge(x,y),z);
    return ans;
}
int main() {
    cin>>n;
    for (ll i = 1,op,v,p,val,x,y,z,l,r;i<=n&&cin>>v>>op;i++) {
        roots[++ver]=roots[v];
        if (op==1){
            cin>>p>>val;
            p^=lstans,val^=lstans;
            split(roots[ver],p,x,y);
            roots[ver]=merge(merge(x,insert(val)),y);
        }else if (op==2) {
            cin>>p;
            p^=lstans;
            split(roots[ver],p,x,z);
            split(x,p-1,x,y);
            roots[ver]=merge(x,z);
        } else if (op==3) {
            cin>>l>>r;
            l^=lstans,r^=lstans;
            split(roots[ver],r,x,z);
            split(x,l-1,x,y);
            tree[y].lzy^=1;
            swap(tree[y].ls,tree[y].rs);
            roots[ver]=merge(merge(x,y),z);
        } else if (op==4) {
            cin>>l>>r;
            l^=lstans,r^=lstans;
            lstans=query_sum(roots[ver],l,r);
            cout<<lstans<<endl;
        }
    }
}

正常 pushdown 函数中是不用新建节点的,但是在这篇代码里面,如果把 pushdown 里面的新建节点代码 tree[++tot]=LS;tree[++tot]=RS; 删掉就会全 WA,求问是为什么

2025/2/8 17:29
加载中...