P5055 【模板】可持久化文艺平衡树

#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5,M=N<<6;
int n,op,a,b,p,x,y,z,tot,rt[N],lc[M],rc[M],val[M],rd[M],sz[M],tg[M],cur,ti[M];
long long sum[M],ans;
void push(int p){
	sz[p]=sz[lc[p]]+sz[rc[p]]+1;
	sum[p]=sum[lc[p]]+sum[rc[p]]+val[p];
}
void copy(int &x){
	if(ti[x]==cur) return ;
	int y=++tot;	//复制节点 x，ti[x] 表示 x 新建时的版本，cur 表示当前版本，在当前版本中新建的点可以不用复制，这样能省一些空间
	lc[y]=lc[x],rc[y]=rc[x],val[y]=val[x],sum[y]=sum[x],
	sz[y]=sz[x],tg[y]=tg[x],rd[y]=rd[x],ti[y]=cur,x=y;
}
void down(int &p){
	copy(p);
	if(tg[p]){ 
		if(lc[p]) copy(lc[p]),tg[lc[p]]^=1;
		if(rc[p]) copy(rc[p]),tg[rc[p]]^=1;
		swap(lc[p],rc[p]),tg[p]=0;
	} 
}
void split(int p,int &x,int &y,int k){
	if(!p){x=y=0;return ;}
	down(p);	//在 down 时 p 已经被复制过了，所以这里不用复制
	if(sz[lc[p]]>=k) split(lc[p],x,lc[y=p],k);
	else split(rc[p],rc[x=p],y,k-sz[lc[p]]-1);
	push(p); 
}
int merge(int x,int y){
	if(!x||!y) return x|y;
	if(rd[x]>rd[y]) return down(x),rc[x]=merge(rc[x],y),push(x),x;
	return down(y),lc[y]=merge(x,lc[y]),push(y),y;
}
signed main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d%d%d",&p,&op,&a),a^=ans,rt[cur=i]=rt[p];
		if(op==2) split(rt[i],x,z,a),split(x,x,y,a-1),rt[i]=merge(x,z);
		else{
			scanf("%d",&b),b^=ans;
			if(op==1){	//!
				split(rt[i],x,y,a),tot++,val[tot]=sum[tot]=b,sz[tot]=1,rd[tot]=rand(),ti[tot]=i;
				rt[i]=merge(merge(x,tot),y);
			} 
			else{
				split(rt[i],x,z,b),split(x,x,y,a-1);
				(op==3?tg[y]^=1:printf("%lld\n",ans=sum[y])),rt[i]=merge(merge(x,y),z);
			}
		}
	}
	return 0;
}

标 ! 处：

if(op==1){
	split(rt[i],x,y,a),tot++,val[tot]=sum[tot]=b,sz[tot]=1,rd[tot]=rand(),ti[tot]=i;
	rt[i]=merge(merge(x,tot),y);
} 

上面这么写可以通过，而如果这么写：

if(op==1){
	tot++,val[tot]=sum[tot]=b,sz[tot]=1,rd[tot]=rand(),ti[tot]=i;
	split(rt[i],x,y,a),rt[i]=merge(merge(x,tot),y);
} 

测样例都被卡住了。不难发现区别仅仅是 split(rt[i],x,y,a) 的位置变化。

求巨佬指点，为什么两种写法不一样 QwQ