平衡树

功能：插入，删除，根据数值查排名，根据排名查数据，找前驱后继

您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：

1. 插入数值 x。

2. 删除数值 x(若有多个相同的数，应只删除一个)。

3. 查询数值 x 的排名(若有多个相同的数，应输出最小的排名)。

4. 查询排名为 x 的数值。

5. 求数值 x 的前驱(前驱定义为小于 x 的最大的数)。

6. 求数值 x 的后继(后继定义为大于 x 的最小的数)。

注意： 数据保证查询的结果一定存在。

输入格式

第一行为 n，表示操作的个数。

接下来 n 行每行有两个数 opt 和 x，opt 表示操作的序号(1≤opt≤6)。

输出格式

对于操作 3,4,5,6 每行输出一个数，表示对应答案。

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+10;
const int INF=1e8;
int n,m;
int root,idx;
struct node
{
	int l,r;
	int cnt,size;
	int key,val;
}t[N];

void pushup(int p)
{
	t[p].size=t[t[p].l].size+t[t[p].r].size+t[p].cnt;
}
void zig(int &p)
{
	int q=t[p].l;
	t[p].l=t[q].r;
	t[q].r=p;p=q;
	pushup(t[p].r);
	pushup(p);
}
void zag(int &p)
{
	int q=t[p].r;
	t[p].r=t[q].l;
	t[q].l=p;p=q;
	pushup(t[p].l);
	pushup(p);
}
int get_node(int key)
{
	t[++idx].key=key;
	t[idx].val=rand();
	t[idx].size=t[idx].cnt=1;
	return idx;
}
void build()
{
	get_node(-INF);get_node(INF);
	root=1;
	t[1].r=2;
	if(t[1].val<t[2].val) zag(root);
	pushup(root);
}
void insert(int &p,int key)
{
	if(!p) p=get_node(key);
	else if(t[p].key==key) t[p].cnt++;
	else if(t[p].key>key)
	{
		insert(t[p].l,key);
		if(t[t[p].l].val>t[p].val) zig(p);
	}
	else
	{
		insert(t[p].r,key);
		if(t[t[p].r].val>t[p].val) zag(p);
	}
	pushup(p);
}
void remove(int &p,int key)
{
	if(!p) return;
	if(t[p].key==key)
	{
		if(t[p].cnt>1) t[p].cnt--;
		else if(t[p].l||t[p].r)
		{
			if(!t[p].r||t[t[p].l].val>t[t[p].r].val)
			{
				zig(p);
				remove(t[p].r,key);
			}
			else
			{
				zag(p);
				remove(t[p].l,key);
			}
		}
		else p=0;
	}
	else if(t[p].key>key) remove(t[p].l,key);
	else remove(t[p].r,key);
	pushup(p);
}
int get_key_by_rank(int p,int rank)
{
	if(!p) return 0;
	if(t[t[p].l].size>=rank) return get_key_by_rank(t[p].l,rank);
	if(t[t[p].l].size+t[p].cnt>=rank) return t[p].key;
	return get_key_by_rank(t[p].r,rank-t[t[p].l].size-t[p].cnt);
}
int get_rank_by_key(int p,int key)
{
	if(!p) return INF;
	if(t[p].key==key) return t[t[p].l].size+1;
	if(t[p].key>key) return get_rank_by_key(t[p].l,key);
	return t[t[p].l].size+t[p].cnt+get_rank_by_key(t[p].r,key);
}
int get_prev(int p,int key)
{
	if(!p) return -INF;
	if(t[p].key>=key) return get_prev(t[p].l,key);
	return max(t[p].key,get_prev(t[p].r,key));
}
int get_next(int p,int key)
{
	if(!p) return INF;
	if(t[p].key<=key) return get_next(t[p].r,key);
	return min(t[p].key,get_next(t[p].l,key));
}


int main(){
	
	build();
    scanf("%d", &n);
    while (n -- )
    {
        int opt, x;
        scanf("%d%d", &opt, &x);
        if (opt == 1) insert(root, x);
        else if (opt == 2) remove(root, x);
        else if (opt == 3) printf("%d\n", get_rank_by_key(root, x) - 1);
        else if (opt == 4) printf("%d\n", get_key_by_rank(root, x + 1));
        else if (opt == 5) printf("%d\n", get_prev(root, x));
        else printf("%d\n", get_next(root, x));
    }

	
	
	return 0;
}