Splay（普通、区间翻转） 模板

Splay_普通

#include<cstdio>
#include<cstring>
using namespace std;
#define N 100010
#define mn 1e+8
struct
{
	int v[2]={0,0},s=0,x=mn,si,fa;
}f[N];
int len=1,root=1,n;
void update(int x)
{
	f[x].si=f[f[x].v[0]].si*(f[x].v[0]>0)+f[f[x].v[1]].si*(f[x].v[1]>0)+f[x].s;
}
int son(int x,int y)
{
	return f[x].v[1]==y;
}
void rotate(int x)
{
	int y=f[x].fa,z=f[y].fa,p=son(y,x),p1=son(z,y);
	f[z].v[p1]=x,f[x].fa=z;
	f[y].v[p]=f[x].v[p^1],f[f[x].v[p^1]].fa=y;
	f[x].v[p^1]=y,f[y].fa=x;
	update(y);
	update(x);
	update(z);
}
void splay(int x,int rt)
{
	while(f[x].fa!=rt)
	{
		int y=f[x].fa,z=f[y].fa;
		if(f[f[x].fa].fa!=rt)
		{
			if(son(y,x)==son(z,y)) rotate(y); else rotate(x);
		}
		rotate(x);
	}
	if(rt==0) root=x;
}
void ins(int k,int x,int fa)
{
	f[k].fa=fa;
	if(f[k].x==mn) f[k].x=x;
	if(f[k].x==x) 
	{
		f[k].s++,f[k].si++;	
		splay(k,0);
		return;
	}
	int p=1;
	if(x<f[k].x) p=0;
	if(!f[k].v[p]) f[k].v[p]=++len;
	ins(f[k].v[p],x,k);
	update(k);
}
int pos(int k,int x)
{
	if(f[k].x==x) return k;
	if(x<f[k].x) return pos(f[k].v[0],x);
	return pos(f[k].v[1],x);
}
int next(int x,int o)
{
	x=pos(root,x);
	splay(x,0);
	int k=f[x].v[o];
	while(k&&f[k].v[o^1]) 
	{
		k=f[k].v[o^1];
	}
	return k;
}
void del(int x)
{
	int la=next(x,0),ne=next(x,1);
	if(la) splay(la,0);
	if(ne) splay(ne,la);
	int k=f[ne].v[0];
	if(!ne) 
	{
		k=f[la].v[1];
		if(f[k].s==1) f[la].v[1]=0;
		else 
		{
			f[k].s--;
			splay(k,0);
		}
	}
	else 
	{
		if(f[k].s==1) f[ne].v[0]=0;
		else 
		{
			f[k].s--;
			splay(k,0);
		}	
	}	
}
int find(int k,int x)
{
	if(x<=f[f[k].v[0]].si*(f[k].v[0]>0)) return find(f[k].v[0],x);
	if(x<=f[f[k].v[0]].si*(f[k].v[0]>0)+f[k].s) return k;
	return find(f[k].v[1],x-f[f[k].v[0]].si*(f[k].v[0]>0)-f[k].s);
}
int main()
{
	int k,x;
	scanf("%d",&n);
	while(n--)
	{
		scanf("%d%d",&k,&x);
		if(k==1) ins(root,x,0);
		else if(k==2) del(x);
		else if(k==3)
		{
			x=pos(root,x);
			splay(x,0);
			printf("%d
",f[f[x].v[0]].si*(f[x].v[0]>0)+1);
		}
		else if(k==4)
		{
			printf("%d
",f[find(root,x)].x);
		}
		else if(k==5)
		{
			ins(root,x,0);
			printf("%d
",f[next(x,0)].x);
			del(x);
		}
		else if(k==6)
		{
			ins(root,x,0);
			printf("%d
",f[next(x,1)].x);
			del(x);
		}
	}
	return 0;
}

Splay_区间翻转

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define N 100010
#define mn 1e+8
struct
{
	int v[2]={0,0},x=mn,si,fa;
}f[N];
int len=1,root=1,n,bz[N],a[N];
void update(int x)
{
	f[x].si=f[f[x].v[0]].si*(f[x].v[0]>0)+f[f[x].v[1]].si*(f[x].v[1]>0)+1;
}
int son(int x,int y)
{
	return f[x].v[1]==y;
}
void rotate(int x)
{
	int y=f[x].fa,z=f[y].fa,p=son(y,x),p1=son(z,y);
	f[z].v[p1]=x,f[x].fa=z;
	f[y].v[p]=f[x].v[p^1],f[f[x].v[p^1]].fa=y;
	f[x].v[p^1]=y,f[y].fa=x;
	update(y);
	update(x);
	update(z);
}
void splay(int x,int rt)
{
	while(f[x].fa!=rt)
	{
		int y=f[x].fa,z=f[y].fa;
		if(f[f[x].fa].fa!=rt)
		{
			if(son(y,x)==son(z,y)) rotate(y); else rotate(x);
		}
		rotate(x);
	}
	if(rt==0) root=x;
}
void ins(int k,int x,int fa)
{
	f[k].fa=fa;
	if(f[k].x==mn) f[k].x=x;
	if(f[k].x==x) 
	{
		f[k].si++;	
		splay(k,0);
		return;
	}
	int p=1;
	if(x<f[k].x) p=0;
	if(!f[k].v[p]) f[k].v[p]=++len;
	ins(f[k].v[p],x,k);
	update(k);
}
int pos(int k,int x)
{
	if(f[k].x==x) return k;
	if(x<f[k].x) return pos(f[k].v[0],x);
	return pos(f[k].v[1],x);
}
int next(int x,int o)
{
	x=pos(root,x);
	splay(x,0);
	int k=f[x].v[o];
	while(k&&f[k].v[o^1]) 
	{
		k=f[k].v[o^1];
	}
	return k;
}
int find(int k,int x)
{
	if(bz[k]) 
	{
		bz[k]^=1;
		swap(f[k].v[0],f[k].v[1]);
		bz[f[k].v[0]]^=1;
		bz[f[k].v[1]]^=1;
	}
	if(x<=f[f[k].v[0]].si*(f[k].v[0]>0)) return find(f[k].v[0],x);
	if(x<=f[f[k].v[0]].si*(f[k].v[0]>0)+1) return k;
	return find(f[k].v[1],x-f[f[k].v[0]].si*(f[k].v[0]>0)-1);
}
void reserve(int l,int r)
{
	splay(find(root,l),0);
	splay(find(root,r+2),root);
	bz[f[f[root].v[1]].v[0]]^=1;
}
int main()
{
	int m,i,l,r;
	scanf("%d%d",&n,&m);
	for(i=1;i<=n;i++) ins(root,i,0);
	ins(root,0,0),ins(root,n+1,0);
	while(m--)
	{
		scanf("%d%d",&l,&r);
		reserve(l,r);
	}
	for(i=1;i<=n;i++) printf("%d ",find(root,i+1));
	return 0;
}