bzoj3224普通平衡樹

一道伸展樹裸題。一直沒做，完善代碼的時候順便刷掉吧…….

Description

您需要寫一種資料結構（可參考題目标題），來維護一些數，其中需要提供以下操作：

1. 插入x數

2. 删除x數(若有多個相同的數，因隻删除一個)

3. 查詢x數的排名(若有多個相同的數，因輸出最小的排名)

4. 查詢排名為x的數

5. 求x的前驅(前驅定義為小于x，且最大的數)

6. 求x的後繼(後繼定義為大于x，且最小的數)

Input

第一行為n，表示操作的個數,下面n行每行有兩個數opt和x，opt表示操作的序号(1<=opt<=6)

Output

對于操作3,4,5,6每行輸出一個數，表示對應答案

Sample Input

10

1 106465

4 1

1 317721

1 460929

1 644985

1 84185

1 89851

6 81968

1 492737

5 493598

Sample Output

106465

84185

492737

HINT

1.n的資料範圍：n<=100000

2.每個數的資料範圍：[-2e9,2e9]

//制作人：陳保良
#include<cstdio>
using namespace std;
int read()
{
	int x=0,f=1;char ch=getchar();
	while(ch<'0' || ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0' && ch<='9'){x=x*10+ch-'0';ch=getchar();}
	return x*f;
}
int root;
struct trnode
{
	int d,c,n,f,son[2];
}tr[110000];int trlen;
void update(int x)
{
	int lc=tr[x].son[0],rc=tr[x].son[1];
	tr[x].c=tr[lc].c+tr[rc].c+tr[x].n;
}
void add(int d,int f)
{
	trlen++;int x=trlen;
	tr[x].d=d;tr[x].c=tr[x].n=1;
	tr[x].f=f;if(d<tr[f].d)tr[f].son[0]=x;else tr[f].son[1]=x;
	tr[x].son[0]=tr[x].son[1]=0;
}
void Rotate(int x,int w)
{
	int f=tr[x].f,ff=tr[f].f;
	int r,R;
	r=tr[x].son[w],R=f;
	tr[R].son[1-w]=r;
	if(r!=0)tr[r].f=R;
	r=x,R=ff;
	if(tr[R].son[0]==f)tr[R].son[0]=r;else tr[R].son[1]=r;
	tr[r].f=R;
	r=f,R=x;
	tr[R].son[w]=r;
	tr[r].f=R;
	update(f);
	update(x);
}
void splay(int x,int rt)
{	
	while(tr[x].f!=rt)
	{
		int f=tr[x].f,ff=tr[f].f;
		if(ff==rt)
		{
			if(tr[f].son[0]==x)Rotate(x,1);
			else Rotate(x,0);
		}
		else
		{
			if(tr[ff].son[0]==f && tr[f].son[0]==x){Rotate(f,1);Rotate(x,1);}
			else if(tr[ff].son[1]==f && tr[f].son[1]==x){Rotate(f,0);Rotate(x,0);}
			else if(tr[ff].son[0]==f && tr[f].son[1]==x){Rotate(x,0);Rotate(x,1);}
			else{Rotate(x,1);Rotate(x,0);}
		}
	}
	if(rt==0)root=x;
}
int findip(int d)
{
	int x=root;
	while(d!=tr[x].d)
	{
		int lc=tr[x].son[0],rc=tr[x].son[1];
		if(d<tr[x].d)
		{
			if(lc==0)break;
			x=lc;
		}
		else
		{
			if(rc==0)break;
			x=rc;
		}
	}
	return x;
}
void ins(int d)
{
	if(root==0)
	{
		add(d,0);
		root=trlen;
		return ;
	}
	int x=findip(d);
	if(d==tr[x].d)
	{
		tr[x].n++;
		update(x);
		splay(x,0);
	}
	else
	{
		add(d,x);
		update(x);
		splay(trlen,0);
	}
}
void del(int d)
{
	int x=findip(d);
	if(tr[x].d!=d)return ;
	splay(x,0);
	if(tr[x].n>1){tr[x].n--;update(x);return ;}
	if(tr[x].son[0]==0 && tr[x].son[1]==0){root=trlen=0;}
	else if(tr[x].son[0]==0){root=tr[x].son[1];tr[root].f=0;}
	else if(tr[x].son[1]==0){root=tr[x].son[0];tr[root].f=0;}
	else
	{
		int p=tr[x].son[0];while(tr[p].son[1]!=0)p=tr[p].son[1];
		splay(p,x);
		int r=tr[x].son[1],R=p;
		tr[R].son[1]=r;
		tr[r].f=R;
		root=R;tr[root].f=0;
		update(R);
	}
}
int findpaiming(int d)
{
	int x=findip(d);splay(x,0);
	return tr[tr[x].son[0]].c+1;
}
int findshuzi(int k)
{
	int x=root;
	while(1)
	{
		int lc=tr[x].son[0],rc=tr[x].son[1];
		if(k<=tr[lc].c)x=lc;
		else if(k>tr[lc].c+tr[x].n){k-=tr[lc].c+tr[x].n;x=rc;}
		else break;
	}
	splay(x,0);
	return tr[x].d;
}
int findqianqu(int d)
{
	int x=findip(d);splay(x,0);
	if(tr[x].d>=d && tr[x].son[0]!=0)
	{
		x=tr[x].son[0];
		while(tr[x].son[1]!=0)x=tr[x].son[1];
	}
	if(tr[x].d>=d)x=0;
	return tr[x].d;
}
int findhouji(int d)
{
	int x=findip(d);splay(x,0);
	if(tr[x].d<=d && tr[x].son[1]!=0)
	{
		x=tr[x].son[1];
		while(tr[x].son[0]!=0)x=tr[x].son[0];
	}
	if(tr[x].d<=d)x=0;
	return tr[x].d;
}
int main()
{
	int n,x,y;
	n=read();
	for(int i=1;i<=n;i++)
	{
		x=read();y=read();
		if(x==1)ins(y);
		else if(x==2)del(y);
		else if(x==3)printf("%d\n",findpaiming(y));
		else if(x==4)
		{
			if(y<=tr[root].c)printf("%d\n",findshuzi(y));
			else printf("-1\n");
		}
		else if(x==5)printf("%d\n",findqianqu(y));
		else printf("%d\n",findhouji(y));
	}
	return 0;
}
           

祝1A