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,求问是为什么