RT，Splay 写挂了，已经调了一下午了 /kk

代码：

#include <stdio.h>

typedef struct {
	int father;
	int cur_cnt;
	int cnt;
	int val;
	int son[7];
} Node;

int cnt = 0, root;
Node tree[100007];

inline int get_son_type(int x){
	return tree[tree[x].father].son[0] == x ? 0 : 1;
}

inline void update(int x){
	tree[x].cnt = tree[tree[x].son[0]].cnt + tree[tree[x].son[1]].cnt + tree[x].cur_cnt;
}

inline void rotate(int x){
	int u = tree[x].father, v = tree[u].father, type = get_son_type(x), type_ = type ^ 1;
	tree[x].father = v;
	if (v == 0){
		root = x;
	} else {
		tree[v].son[get_son_type(u)] = x;
	}
	tree[u].son[type] = tree[x].son[type_];
	tree[tree[u].son[type]].father = u;
	tree[u].father = x;
	tree[x].son[type_] = u;
	update(u);
	update(x);
}

inline void splay(int x){
	while (tree[x].father != 0){
		int u = tree[x].father;
		if (tree[u].father != 0){
			if (get_son_type(x) != get_son_type(u)){
				rotate(x);
			} else {
				rotate(u);
			}
		}
		rotate(x);
	}
	root = x;
}

inline int insert(int x){
	if (root == 0){
		root = ++cnt;
		tree[cnt].cur_cnt = tree[cnt].cnt = 1;
		tree[cnt].val = x;
		return cnt;
	}
	int i = root;
	while (i != 0){
		tree[i].cnt++;
		if (x < tree[i].val){
			if (tree[i].son[0] != 0){
				i = tree[i].son[0];
			} else {
				tree[i].son[0] = ++cnt;
				break;
			}
		} else if (x == tree[i].val){
			tree[i].cur_cnt++;
			splay(i);
			return i;
		} else if (tree[i].son[1] != 0){
			i = tree[i].son[1];
		} else {
			tree[i].son[1] = ++cnt;
			break;
		}
	}
	tree[cnt].father = i;
	tree[cnt].cur_cnt = tree[cnt].cnt = 1;
	tree[cnt].val = x;
	splay(cnt);
	return cnt;
}

inline int find(int x){
	for (int i = root; i != 0; ){
		if (x == tree[i].val) return i;
		if (x < tree[i].val){
			i = tree[i].son[0];
		} else {
			i = tree[i].son[1];
		}
	}
	return 0;
}

inline int get_max(int x){
	while (tree[x].son[1] != 0) x = tree[x].son[1];
	return x;
}

inline void erase(int x){
	int u = find(x);
	if (u != 0){
		if (tree[u].cur_cnt == 1){
			int ls, rs;
			splay(u);
			ls = tree[u].son[0];
			rs = tree[u].son[1];
			tree[u].son[0] = tree[u].son[1] = tree[ls].father = tree[rs].father = 0;
			if (ls == 0){
				root = rs;
			} else {
				int v = get_max(ls);
				root = ls;
				splay(v);
				tree[v].father = 0;
				tree[v].son[1] = rs;
				tree[rs].father = v;
				update(v);
			}
		} else {
			tree[u].cur_cnt--;
			tree[u].cnt--;
		}
	}
}

inline int get_rank(int x){
	int ans = tree[tree[insert(x)].son[0]].cnt + 1;
	erase(x);
	return ans;
}

inline int get_kth_number(int x){
	if (x > tree[root].cnt) return -1;
	for (int i = root; i != 0; ){
		if (x <= tree[tree[i].son[0]].cnt){
			i = tree[i].son[0];
		} else {
			x -= tree[tree[i].son[0]].cnt + tree[i].cur_cnt;
			if (x <= 0) return tree[i].val;
			i = tree[i].son[1];
		}
	}
}

inline int get_prev(int x){
	int ans;
	ans = tree[get_max(tree[insert(x)].son[0])].val;
	erase(x);
	return ans;
}

inline int get_min(int x){
	while (tree[x].son[0] != 0) x = tree[x].son[0];
	return x;
}

inline int get_next(int x){
	int ans;
	ans = tree[get_min(tree[insert(x)].son[1])].val;
	erase(x);
	return ans;
}

int main(){
	int n;
	scanf("%d", &n);
	for (int i = 1; i <= n; i++){
		int opt, x;
		scanf("%d %d", &opt, &x);
		if (opt == 1){
			insert(x);
		} else if (opt == 2){
			erase(x);
		} else if (opt == 3){
			printf("%d\n", get_rank(x));
		} else if (opt == 4){
			printf("%d\n", get_kth_number(x));
		} else if (opt == 5){
			printf("%d\n", get_prev(x));
		} else {
			printf("%d\n", get_next(x));
		}
	}
	return 0;
}