#include <bits/stdc++.h>
#define maxn 500003
#define inf 2147483647
using namespace std;

struct SPLAY {
	public:
		struct node {
			int son[2], fa, cnt, val, sz;
			node(int ls, int rs, int fa, int cnt, int sz, int val):
				son({ls, rs}), fa(fa), cnt(cnt), sz(sz), val(val) {}
			node() {}
		} v[maxn];
		int tot, root;
		inline int New(const node x) {
			v[++tot] = x;
			return tot;
		}
		inline void s_clear(int p) {
			v[p] = node(0, 0, 0, 0, 0, 0);
		}
		inline bool which(int p) {
			return v[v[p].fa].son[1] == p;
		}
		inline void update(int p) {
			if (p) {
				v[p].sz = v[p].cnt;
				if (v[p].son[0]) {
					v[p].sz += v[v[p].son[0]].sz;
				}
				if (v[p].son[1]) {
					v[p].sz += v[v[p].son[1]].sz;
				}
			}
		}
		inline void rotate(int p) {
			int f = v[p].fa, gf = v[f].fa;
			if (f) {
				bool w = which(p);
				v[f].son[w] = v[p].son[!w];
				v[v[f].son[w]].fa = f;
				v[f].fa = p;
				v[p].son[!w] = f;
				v[p].fa = gf;
				if (gf) {
					v[gf].son[v[gf].son[1] == f] = p;
				}
				update(f);
				update(p);
			}
		}
		inline void splay(int p, int tar) {
			for (int f; (f = v[p].fa) != tar && (v[p].fa); rotate(p)) {
				if (v[f].fa != tar) {
					rotate(which(p) == which(f) ? f : p);
				}
			}
			rotate(p);
			if (tar == root) {
				root = p;
			}
		}
		inline void insert(int val) {
			if (!root) {
				root = New(node(0, 0, 0, 1, 1, val));
				return;
			}
			int now = root, last = 0;
			while (true) {
				if (now && val == v[now].val) {
					++v[now].cnt;
					update(now);
					update(last);
					splay(now, root);
					return;
				} else {
					last = now;
					now = v[now].son[v[now].val < val];
					if (!now) {
						now = New(node(0, 0, last, 1, 1, val));
						v[last].son[v[last].val < val] = now;
						update(last);
						splay(now, root);
						return;
					}
				}
			}
		}
		inline int get_rank(int val) {
			int ans = 0, now = root;
			while (now) {
				if (val < v[now].val) {
					now = v[now].son[0];
				} else {
					ans += (v[now].son[0] ? v[v[now].son[0]].sz : 0);
					if (v[now].val == val) {
						splay(now, root);
						return ans;
					}
					ans += v[now].cnt;
					now = v[now].son[1];
				}
			}
			return ans;
		}
		inline int get_val(int rank) {
			int now = root;
			while (true) {
				if (rank <= v[v[now].son[0]].sz) {
					now = v[now].son[0];
				} else {
					int tmp = v[now].son[0] ? v[v[now].son[0]].sz : 0;
					tmp += v[now].cnt;
					if (tmp >= rank) {
						return now;
					}
					rank -= tmp;
					now = v[now].son[1];
				}
			}
		}
		inline int find(int val) {
			int now = root, last;
			while (true) {
				if (v[now].val == val) {
					return now;
				}
				last = now;
				now = v[now].son[v[now].val < val];
				if (!now) {
					printf("Runtime error:节点不存在.");
					exit(0);
				}
			}
		}
		inline int get_pre(int val) {
			int it = root, now = root, ans = -inf;
			while (now) {
				if (val == v[now].val) {
					if (v[now].son[0]) {
						now = v[now].son[0];
						while (v[now].son[1]) {
							now = v[now].son[1];
						}
						it = now;
					}
					break;
				}
				if (v[now].val > ans && v[now].val < val) {
					it = now;
					ans = v[now].val;
				}
				now = v[now].son[v[now].val < val];
			}
			return it;
		}
		inline int get_nex(int val) {
			int now = root, it = root, ans = inf;
			while (now) {
				if (v[now].val == val) {
					if (v[now].son[1]) {
						now = v[now].son[1];
						while (v[now].son[0]) {
							now = v[now].son[0];
						}
						it = now;
					}
					break;
				}
				now = v[now].son[v[now].val < val];
				if (ans > v[now].val && v[now].val > val) {
					it = now;
					ans = v[now].val;
				}
			}
			return it;
		}
		inline void Delete(int val) {
			int it = find(val);
			if (it == root) {
				if (v[it].cnt > 1) {
					--v[it].cnt;
					update(it);
				} else if (!v[it].son[0] && !v[it].son[1]) {
					s_clear(it);
					root = 0;
				} else if (!v[it].son[0]) {
					root = v[it].son[1];
					v[root].fa = 0;
					s_clear(it);
				} else if (!v[it].son[1]) {
					root = v[it].son[0];
					v[root].fa = 0;
					s_clear(it);
				} else {
					int pre = get_pre(val);
					splay(pre, root);
					v[pre].son[1] = v[it].son[1];
					v[v[it].son[1]].fa = pre;
					update(pre);
					s_clear(it);
					root = pre;
				}
				return;
			}
			if (v[it].cnt > 1) {
				--v[it].cnt;
				update(it);
				splay(it, root);
			} else if (!v[it].son[0] && !v[it].son[1]) {
				int f = v[it].fa;
				v[f].son[which(it)] = 0;
				s_clear(it);
				update(f);
				splay(f, root);
			} else if (!v[it].son[0]) {
				int f = v[it].fa;
				v[f].son[which(it)] = v[it].son[1];
				v[v[it].son[1]].fa = f;
				s_clear(it);
				update(f);
				splay(f, root);
			} else if (!v[it].son[1]) {
				int f = v[it].fa;
				v[f].son[which(it)] = v[it].son[0];
				v[v[it].son[0]].fa = f;
				s_clear(it);
				update(f);
				splay(f, root);
			} else {
				int pre = get_pre(val);
				splay(pre, it);
				v[pre].son[1] = v[it].son[1];
				v[v[it].son[1]].fa = pre;
				s_clear(it);
				update(pre);
				splay(pre, root);
			}
		}
		inline void print(int u) {
  			//查错用，输出整棵树。
			if (v[u].son[0]) {
				print(v[u].son[0]);
			}
			if (u) {
				printf("%d ", v[u].val);
			}
			if (v[u].son[1]) {
				print(v[u].son[1]);
			}
		}
} ANS;

inline int read() {
	int x = 0;
	bool f = false;
	char c = getchar();
	while (c < '0' || c > '9') {
		if (c == '-') {
			f = true;
		}
		c = getchar();
	}
	while (c >= '0' && c <= '9') {
		x = x * 10 + c - '0';
		c = getchar();
	}
	return f ? -x : x;
}
int n, pos, x, put;

int main() {
	n = read();
	while (n--) {
		pos = read(), x = read();
		if (pos == 1) {
			ANS.insert(x);
		}
		if (pos == 2) {
			ANS.Delete(x);
		}
		if (pos == 3) {
			put = ANS.get_rank(x) + 1;
			if (put) {
				printf("%d\n", put);
			} else {
				putchar('0'), putchar('\n');
			}
		}
		if (pos == 4) {
			put = ANS.v[ANS.get_val(x)].val;
			if (put) {
				printf("%d\n", put);
			} else {
				putchar('0'), putchar('\n');
			}
		}
		if (pos == 5) {
			put = ANS.v[ANS.get_pre(x)].val;
			if (put) {
				printf("%d\n", put);
			} else {
				putchar('0'), putchar('\n');
			}
		}
		if (pos == 6) {
			put = ANS.v[ANS.get_nex(x)].val;
			if (put) {
				printf("%d\n", put);
			} else {
				putchar('0'), putchar('\n');
			}
		}
	}
	return 0;
}

提交记录

注意

Splay 是将节点 p，旋转顶替 tar。而非旋转成为 tar 的子节点。