Problem
有以下操作
- 插入x数
- 删除x数(若有多个相同的数，因只删除一个)
- 查询x数的排名(若有多个相同的数，因输出最小的排名)
- 查询排名为x的数
- 求x的前驱(前驱定义为小于x，且最大的数)
- 求x的后继(后继定义为大于x，且最小的数)
Solution
裸的Splay:
Rotate旋转操作 Splay伸展操作Notice
注意，删除的时候不是把这个元素都删除，而是删除一个！！！
Code
#include#include #include #include #include using namespace std;#define sqz main#define ll long long#define reg register int#define rep(i, a, b) for (reg i = a; i <= b; i++)#define per(i, a, b) for (reg i = a; i >= b; i--)#define travel(i, u) for (reg i = head[u]; i; i = edge[i].next)const int INF = 1e9, N = 100000;const double eps = 1e-6, phi = acos(-1);ll mod(ll a, ll b) {if (a >= b || a < 0) a %= b; if (a < 0) a += b; return a;}ll read(){ ll x = 0; int zf = 1; char ch; while (ch != '-' && (ch < '0' || ch > '9')) ch = getchar();if (ch == '-') zf = -1, ch = getchar(); while (ch >= '0' && ch <= '9') x = x * 10 + ch - '0', ch = getchar(); return x * zf;}void write(ll y) { if (y < 0) putchar('-'), y = -y; if (y > 9) write(y / 10); putchar(y % 10 + '0');}int point = 0, root, pre, suf, ans;struct node{ int val[N + 5], count[N + 5], num[N + 5], son[2][N + 5], parent[N + 5]; inline void up(int u) { count[u] = count[son[0][u]] + count[son[1][u]] + num[u]; } void Rotate(int x, int &rt) { int y = parent[x], z = parent[y]; int l = (son[1][y] == x), r = 1 - l; if (y == rt) rt = x; else if (son[0][z] == y) son[0][z] = x; else son[1][z] = x; parent[x] = z; parent[son[r][x]] = y, son[l][y] = son[r][x]; parent[y] = x, son[r][x] = y; up(y); up(x); } void Splay(int x, int &rt) { while (x != rt) { int y = parent[x], z = parent[y]; if (y != rt) { if ((son[0][z] == y) ^ (son[0][y] == x)) Rotate(x, rt); else Rotate(y, rt); } Rotate(x, rt); } } void Insert(int &u, int x, int last) { if (u == 0) { u = ++point; val[u] = x, parent[u] = last, num[u] = count[u] = 1; Splay(u, root); } else { if (x > val[u]) Insert(son[1][u], x, u); else if (x < val[u]) Insert(son[0][u], x, u); else if (x == val[u]) num[u]++, count[u]++, Splay(u, root); } } void Delete(int x) { Splay(x, root); if (num[x] > 1) { num[x]--, count[x]--; return; } if (son[0][x] * son[1][x] == 0) root = son[0][x] + son[1][x]; else { int t = son[1][x]; while (son[0][t] != 0) t = son[0][t]; Splay(t, root); son[0][t] = son[0][x], parent[son[0][x]] = t; up(t); } parent[root] = 0; } void Find_pre(int u, int x) { if (u == 0) return; if (x > val[u]) { pre = u; Find_pre(son[1][u], x); ans += count[son[0][u]] + num[u]; } else Find_pre(son[0][u], x); } void Find_suf(int u,int x) { if (u == 0) return; if (x < val[u]) { suf = u; Find_suf(son[0][u], x); } else Find_suf(son[1][u], x); } int Find_num(int u, int x) { if (x <= count[son[0][u]]) return Find_num(son[0][u], x); if (x > count[son[0][u]] + num[u]) return Find_num(son[1][u], x - count[son[0][u]] - num[u]); return val[u]; } int Find_rank(int x) { ans = 0; Find_pre(root, x); return ans + 1; } int Find_id(int u, int x) { if (x == val[u]) return u; if (x > val[u]) return Find_id(son[1][u], x); if (x < val[u]) return Find_id(son[0][u], x); }}splay_tree;int sqz(){ int n = read(); root = 0; rep(i, 1, n) { int op = read(), t = read(); switch (op) { case 1: { splay_tree.Insert(root, t, 0); break; } case 2: { int x = splay_tree.Find_id(root, t); splay_tree.Delete(x); break; } case 3: { printf("%d\n", splay_tree.Find_rank(t)); break; } case 4: { printf("%d\n", splay_tree.Find_num(root, t)); break; } case 5: { splay_tree.Find_pre(root, t); printf("%d\n", splay_tree.val[pre]); break; } case 6: { splay_tree.Find_suf(root, t); printf("%d\n", splay_tree.val[suf]); break; } } } return 0;}