指针版

数组版

#include<bits/stdc++.h>
using namespace std;
int n,root[200005],a[25600005],c[25600005],e[25600005],l[25600005],r[25600005],cnt=0,bn,k,x,y;
long long b[25600005],ans=0;
bool d[25600005];
int copy(int x)
{
	a[++cnt]=a[x];
	b[cnt]=b[x];
	c[cnt]=c[x];
	d[cnt]=d[x];
	e[cnt]=(rand()<<15)+rand();
	l[cnt]=l[x];
	r[cnt]=r[x];
	return cnt;
}
void pushdown(int x)
{
	if (d[x])
	{
		if (l[x])
		{
			l[x]=copy(l[x]);
			swap(l[l[x]],r[l[x]]);
			d[l[x]]^=1;
		}
		if (r[x])
		{
			r[x]=copy(r[x]);
			swap(l[r[x]],r[r[x]]);
			d[r[x]]^=1;
		}
		d[x]=0;
	}
}
int merge(int x,int y)
{
	if (x && y)
	{
		if (e[x]<e[y])
		{
			pushdown(x);
			r[x]=merge(r[x],y);
			b[x]=a[x]+b[l[x]]+b[r[x]];
			c[x]=c[l[x]]+c[r[x]]+1;
			return x;
		}
		else
		{
			pushdown(y);
			l[y]=merge(x,l[y]);
			b[y]=a[y]+b[l[y]]+b[r[y]];
			c[y]=c[l[y]]+c[r[y]]+1;
			return y;
		}
	}
	else
	return x+y;
}
void split(int x,int &y,int &z,int k)
{
	if (x)
	{
		pushdown(x);
		x=copy(x);
		if (c[l[x]]<k)
		{
			y=x;
			split(r[x],r[x],z,k-c[l[x]]-1);
		}
		else
		{
			z=x;
			split(l[x],y,l[x],k);
		}
		b[x]=a[x]+b[l[x]]+b[r[x]];
		c[x]=c[l[x]]+c[r[x]]+1;
	}
	else
	{
		y=0;
		z=0;
	}
}
void insert(int old,int nw,int k,int num)
{
	int x,y=++cnt,z;
	a[cnt]=num;
	b[cnt]=num;
	c[cnt]=1;
	e[cnt]=(rand()<<15)+rand();
	split(root[old],x,z,k);
	root[nw]=merge(merge(x,y),z);
}
void erase(int old,int nw,int num)
{
	int x,y,z;
	split(root[old],x,z,num);
	split(x,x,y,num-1);
	if (y)
	y=merge(l[y],r[y]);
	root[nw]=merge(merge(x,y),z);
}
void modify(int old,int nw,int num1,int num2)
{
	int x,y,z;
	split(root[old],x,z,num2);
	split(x,x,y,num1-1);
	if (y)
	{
		swap(l[y],r[y]);
		d[y]^=1;
	}
	root[nw]=merge(merge(x,y),z);
}
long long query(int old,int nw,int num1,int num2)
{
	int x,y,z;
	split(root[old],x,z,num2);
	split(x,x,y,num1-1);
	long long result=b[y];
	root[nw]=merge(merge(x,y),z);
	return result;
}
int main()
{
	srand(time(nullptr));
	cin>>n;
	for (int i=1;i<=n;++i)
	{
		scanf("%d%d",&bn,&k);
		if (k==1)
		{
			scanf("%d%d",&x,&y);
			insert(bn,i,x^ans,y^ans);
		}
		else if (k==2)
		{
			scanf("%d",&x);
			erase(bn,i,x^ans);
		}
		else if (k==3)
		{
			scanf("%d%d",&x,&y);
			modify(bn,i,x^ans,y^ans);
		}
		else
		{
			scanf("%d%d",&x,&y);
			ans=query(bn,i,x^ans,y^ans);
			cout<<ans<<'\n';
		}
	}
}