【BZOJ3224】Tyvj1728普通平衡樹

題意：寫一種資料結構，來維護一些數，其中需要提供以下操作：

1. 插入x數

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

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

4. 查詢排名為x的數

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

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

ps.題目題意很清楚

明顯可以看出是平衡樹，我寫的是splay，删點時就将點旋轉到根，然後就好了。。。

比較坑的是前驅後繼輸入的數在之前并沒有出現過。。。然後注意查詢排名時要最小的就行了。。

#include <iostream>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <queue>
#define ll long long
#define gc getchar()
#define inf 1000000000
#define N 2000009
using namespace std;
int root;
int father[N],son[N][2],v[N],size[N],cnt=2,flag=1;
int read()
{
	int x=0,f=1;
	char ch;
	for (;ch<'0'||ch>'9';ch=gc)
		if (ch=='-') f=-1;
    for (;ch>='0'&&ch<='9';ch=gc)
		x=x*10+ch-'0';
	return x*f;
}
void newnode(int &x,int val,int fa)
{
	x=++cnt;
	v[x]=val;
	size[x]=1;
	father[x]=fa;
	son[x][0]=son[x][1]=0;
}
int find(int val,int k)
{
	int x=root;
	while (son[x][v[x]<val])
	{
		if (k&&v[x]==val) return x;
		x=son[x][v[x]<val];
	}
	return x;
}
void up(int x)
{
	size[x]=size[son[x][0]]+size[son[x][1]]+1;
}
void rotate(int x)
{
	int y=father[x],k=(son[y][0]==x);
	son[y][!k]=son[x][k];
	father[son[y][!k]]=y;
	father[x]=father[y];
	if (father[y]) son[father[y]][son[father[y]][1]==y]=x;
	son[x][k]=y;
	father[y]=x;
	up(y);
}
void splay(int x,int g)
{
	for (int y;(y=father[x])!=g;rotate(x))
		if (father[y]!=g) rotate(((x==son[y][0])==(y==son[father[y]][0]))?y:x);
	up(x);
	if (!g) root=x;
}
void del(int x)
{
	splay(x,0);
	int now=son[root][1];
	while (son[now][0]) now=son[now][0];
	splay(now,root);
	son[now][0]=son[root][0];
	father[son[root][0]]=now;
	father[now]=0;
	root=now;
}
int qry1(int x,int cur)
{
	if (x>v[cur]&&!son[cur][1]) return inf;
	if (x==v[cur]) return min(size[son[cur][0]]+1,qry1(x,son[cur][0]));
	if (x<v[cur]) return qry1(x,son[cur][0]);
	if (x>v[cur]) return size[son[cur][0]]+1+qry1(x,son[cur][1]);
}
int qry2(int x,int cur)
{
	if (x==size[son[cur][0]]+1) return v[cur];
	if (x<size[son[cur][0]]+1) return qry2(x,son[cur][0]);
	if (x>size[son[cur][0]]+1) return qry2(x-size[son[cur][0]]-1,son[cur][1]);
}
int find1(int x,int now)
{
	if (x>v[now]&&!son[now][1]) return inf;
	if (x<v[now]&&!son[now][0]) return v[now];
	if (x<v[now]) return min(v[now],find1(x,son[now][0]));
	if (x>=v[now])return find1(x,son[now][1]);
}
int find2(int x,int now)
{
	if (x<v[now]&&!son[now][0]) return -inf;
	if (x>v[now]&&!son[now][1]) return v[now];
	if (x>v[now]) return max(v[now],find2(x,son[now][1]));
	if (x<=v[now])return find2(x,son[now][0]);
}
int main()
{
	freopen("1.in","r",stdin);
	freopen("1.out","w",stdout);
	int m=read();
	root=1;
	son[0][0]=1;
	son[1][1]=2;
	v[1]=-inf;
	v[2]=inf;
	size[2]=1;
	size[1]=2;
	father[2]=1;
	father[1]=0;
	while (m--)
	{
		int x=read(),y=read(),z,yy;
		switch (x)
		{
			case 1:
				z=find(y,0);
				newnode(son[z][v[z]<y],y,z);
				splay(son[z][v[z]<y],0);
				while (son[x][0]) x=son[x][0];
				break;
			case 2:
				del(find(y,1));
				break;
			case 3:
				printf("%d\n",qry1(y,root)-1);
				break;
			case 4:
				printf("%d\n",qry2(y+1,root));
				break;
			case 5:
				yy=find2(y,root);
				printf("%d\n",yy);
				break;
			case 6:
				yy=find1(y,root);
				printf("%d\n",yy);
				break;
		}
	}
	return 0;
}
           

不要吐槽過程名。我洋文不好。。。。。