题面传送门
比原来平衡树多了一个可持久化操作。
我们考虑和线段树一样可持久化，就是对于每个新访问到的点多新增一个节点和原来的版本区别开来。
这里有几个注意事项:
下推标记的时候要可持久化。merge的时候因为split一定已经可持久化过了所以不用新开节点。
时空复杂度\(O(nlogn)\)
code:

#include<bits/stdc++.h>
#define I inline
#define max(a,b) ((a)>(b)?(a):(b))
#define min(a,b) ((a)<(b)?(a):(b))
#define abs(x) ((x)>0?(x):-(x))
#define re register
#define ll long long
#define db double
#define N 250000
#define M 1000000
#define mod 10007
#define eps (1e-5)
#define U unsigned int
#define it iterator
#define Gc() getchar() 
#define Me(x,y) memset(x,y,sizeof(x))
#define d(x,y) (n*(x-1)+(y))
using namespace std;
int n,op,z,root[N+5];ll lastans,x,y;
struct FHQ_Treap{
	int l[N+5<<7],r[N+5<<7],siz[N+5<<7],cnt,root1,root2,root3,key[N+5<<7],val[N+5<<7],Fl[N+5<<7];ll F[N+5<<7];
	I void Up(int now){F[now]=val[now]+F[l[now]]+F[r[now]];siz[now]=siz[l[now]]+siz[r[now]]+1;}
	I int newnode(int x){val[++cnt]=x;key[cnt]=rand()*rand();Up(cnt);return cnt;}I void memcpy(int &x,int y){l[y]=l[x];r[y]=r[x];siz[y]=siz[x];key[y]=key[x];val[y]=val[x];F[y]=F[x];Fl[y]=Fl[x];x=y;}
	I void push(int now){if(!Fl[now])return;l[now]&&(memcpy(l[now],++cnt),0);r[now]&&(memcpy(r[now],++cnt),0);swap(l[now],r[now]);l[now]&&(Fl[l[now]]^=1);r[now]&&(Fl[r[now]]^=1);Fl[now]=0;}
	I void split(int x,int now,int &a,int &b){
		if(!now) return (void)(a=b=0);push(now);memcpy(now,++cnt);x>=siz[l[now]]+1?(a=now,split(x-1-siz[l[now]],r[a],r[a],b)):(b=now,split(x,l[b],a,l[b]) );Up(now);
	}
	I int merge(int x,int y){
		if(!x||!y) return x|y;push(x);push(y);return key[x]<key[y]?(r[x]=merge(r[x],y),Up(x),x):(l[y]=merge(x,l[y]),Up(y),y);
	}
	I void insert(int x,int y,int id){split(x,root[id],root1,root2);root[id]=merge(root1,merge(newnode(y),root2));}
	I void del(int x,int id){split(x-1,root[id],root1,root2);split(1,root2,root2,root3);root[id]=merge(root1,root3);}
	I void GetF(int x,int y,int id){split(x-1,root[id],root1,root2);split(y-x+1,root2,root2,root3);Fl[root2]^=1;root[id]=merge(merge(root1,root2),root3);}
	I ll find(int x,int y,int id){split(x-1,root[id],root1,root2);split(y-x+1,root2,root2,root3);ll now=F[root2];root[id]=merge(root1,merge(root2,root3));return now;}
}T;
int main(){
	freopen("1.in","r",stdin);freopen("1.out","w",stdout);
	re int i;scanf("%d",&n);for(i=1;i<=n;i++){
		scanf("%d%d%lld",&z,&op,&x);x^=lastans;op^2&&(scanf("%lld",&y),y^=lastans);/*printf("%d %d %d %d\n",op,z,x,y);*/root[i]=root[z];if(op==1) T.insert(x,y,i);if(op==2)T.del(x,i);if(op==3) T.GetF(x,y,i);if(op==4) printf("%lld\n",lastans=T.find(x,y,i)); 
	}
}