普通平衡树
【问题描述】
您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：
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每行输出一个数，表示对应答案
【样例输入】
10
1 106465
4 1
1 317721
1 460929
1 644985
1 84185
1 89851
6 81968
1 492737
5 493598
【样例输出】
106465
84185
492737
【数据范围】
1.n的数据范围：n<=100000
2.每个数的数据范围：[-2e9,2e9]
题解：
裸平衡树
删除操作稍微注意一下就好了
#include<cmath> #include<cstdio> #include<cstdlib> #include<cstring> #include<iostream> #include<algorithm> using namespace std; const int maxn = 1e6; int n; int sma, big; int num, root; int lc[maxn], rc[maxn], fat[maxn]; int si[maxn], cnt[maxn], val[maxn]; inline void Print(int k) { if(!k) return; Print(lc[k]); printf("%d ", val[k]); Print(rc[k]); } inline void Printtree(int k) { if(!k) return; printf("k=%d lc=%d rc=%d fat=%d val=%d ", k, lc[k], rc[k], fat[k], val[k]); Printtree(lc[k]); Printtree(rc[k]); } inline void Scan(int &x) { char c; bool o = false; while(!isdigit(c = getchar())) o = (c != '-') ? o : true; x = c - '0'; while(isdigit(c = getchar())) x = x * 10 + c - '0'; if(o) x = -x; } inline void Update(int x) { si[x] = si[lc[x]] + si[rc[x]] + cnt[x]; } inline void Turn(int x) { int y = fat[x], z = fat[y]; int w = (lc[y] != x) ? lc[x] : rc[x]; fat[x] = z; fat[y] = x; if(w) fat[w] = y; if(z) { if(lc[z] == y) lc[z] = x; else rc[z] = x; } if(lc[y] == x) rc[x] = y, lc[y] = w; else lc[x] = y, rc[y] = w; Update(y); } inline void Splay(int x, int anc) { while(fat[x] != anc) { if(fat[fat[x]] != anc) if((lc[fat[x]] == x) == (lc[fat[fat[x]]] == fat[x])) Turn(fat[x]); else Turn(x); Turn(x); } if(!anc) root = x; Update(x); } inline int Insert(int x) { int f, d = 2, k = root; while(true) { if(!k) { si[++num] = 1; cnt[num] = 1; fat[num] = f; val[num] = x; if(d == 0) lc[f] = num; if(d == 1) rc[f] = num; Splay(num, 0); return num; } ++si[k]; if(x == val[k]) { ++cnt[k]; Splay(k, 0); return k; } f = k; if(x < val[k]) d = 0, k = lc[k]; else d = 1, k = rc[k]; } } inline int Findnum(int x) { int k = root; while(true) { if(x == val[k]) return k; if(x < val[k]) k = lc[k]; else k = rc[k]; } } inline void Clear(int x) { lc[x] = rc[x] = fat[x] = 0; } inline void Del(int x) { int k = Findnum(x); --cnt[k]; Splay(k, 0); if(cnt[k]) return; int s = lc[k]; while(rc[s]) s = rc[s]; if(s) { Splay(s, k); rc[s] = rc[k]; fat[rc[k]] = s; root = s; fat[s] = 0; } else { root = rc[k]; fat[rc[k]] = 0; } Clear(k); } inline int Findval(int x) { int k = root, sum; while(true) { sum = si[lc[k]] + cnt[k]; if(si[lc[k]] < x && x <= sum) return val[k]; if(x > sum) k = rc[k], x -= sum; else k = lc[k]; } } inline int Findrank(int x) { int k = root, sum, ans = 0; while(true) { sum = si[lc[k]] + cnt[k]; if(x == val[k]) return ans + si[lc[k]] + 1; if(x < val[k]) k = lc[k]; else k = rc[k], ans += sum; } } inline int Pre(int x) { int k = root, ans; while(k) { if(x > val[k]) ans = val[k], k = rc[k]; else k = lc[k]; } return ans; } inline int Next(int x) { int k = root, ans; while(k) { if(x < val[k]) ans = val[k], k = lc[k]; else k = rc[k]; } return ans; } int main() { Scan(n); int opt, x; while(n--) { Scan(opt), Scan(x); switch(opt) { case 1: { int k = Insert(x); break; } case 2: { Del(x); break; } case 3: { printf("%d ", Findrank(x)); break; } case 4: { printf("%d ", Findval(x)); break; } case 5: { printf("%d ", Pre(x)); break; } case 6: { printf("%d ", Next(x)); break; } } } }