Description
您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作： 1. 插入x数 2. 删除x数(若有多个相同的数，因只删除一个) 3. 查询x数的排名(若有多个相同的数，因输出最小的排名) 4. 查询排名为x的数 5. 求x的前驱(前驱定义为小于x，且最大的数) 6. 求x的后继(后继定义为大于x，且最小的数)
Input
第一行为n，表示操作的个数,下面n行每行有两个数opt和x，opt表示操作的序号(1<=opt<=6)
Output
对于操作3,4,5,6每行输出一个数，表示对应答案
Sample Input
10 1 106465 4 1 1 317721 1 460929 1 644985 1 84185 1 89851 6 81968 1 492737 5 493598
Sample Output
106465 84185 492737
HINT
1.n的数据范围：n<=100000 2.每个数的数据范围：[-1e7,1e7]
终于打完了splay， 不过还是全程抄代码。 %%%DQS，您是我们的红太阳！没有您我们会死！
#include<iostream> #include<cstdio> using namespace std; typedef long long LL; const int SZ = 1000010; const int INF = 1000000010; struct node { node *ch[2], *f; int sz, cnt, v; void maintain() { sz = cnt + ch[0] -> sz + ch[1] -> sz; } int cmp(int x) { if(x == v) return -1; return x < v ? 0 : 1; } int dir() { return f -> ch[1] == this; } void setc(node *x, int d) { (ch[d] = x) -> f = this; } }T[SZ], *root, *null; int Tcnt = 0; node* newnode(int x, node *f) { node *k = T + (++ Tcnt); k -> v = x; k -> ch[0] = k -> ch[1] = null; k -> sz = k -> cnt = 1; k -> f = f; return k; } void rotate(node *p) { node *fa = p -> f; int d = p -> dir(); fa -> f -> setc(p, fa -> dir()); fa -> setc(p -> ch[d ^ 1], d); fa -> maintain(); p -> setc(fa, d ^ 1); p -> maintain(); if(fa == root) root = p; } void splay(node *p, node *rt = null) { while(p -> f != rt) { if(p -> f -> f == rt) rotate(p); else { if(p -> dir() == p -> f -> dir()) rotate(p -> f), rotate(p); else rotate(p), rotate(p); } } p -> maintain(); } void insert(node *p, int x) { if(root == null) { root = newnode(x, null); return ; } while(p != null) { p -> sz ++; int d = p -> cmp(x); if(d == -1) { p -> cnt ++; break; } if(p -> ch[d] == null) { p -> ch[d] = newnode(x, p); p = p -> ch[d]; break; } p = p -> ch[d]; } splay(p); } void erase(node *p, int x) { while(p != null) { p -> sz --; int d = p -> cmp(x); if(d == -1) { p -> cnt --; break; } p = p -> ch[d]; } if(p -> cnt) return ; splay(p); if(p -> ch[0] == null) { root = p -> ch[1]; root -> f = null; return ; } if(p -> ch[1] == null) { root = p -> ch[0]; root -> f = null; return ; } p = p -> ch[0]; while(p -> ch[1] != null) p = p -> ch[1]; splay(p, root); p -> ch[1] = root -> ch[1]; p -> ch[1] -> f = p; p -> f = null; p -> maintain(); root = p; } int ask_rank(node *p, int x) { int ans = 0; while(p != null) { int d = p -> cmp(x); if(d == -1) return ans + p -> ch[0] -> sz + 1; if(d == 1) ans += p -> ch[0] -> sz + p -> cnt; p = p -> ch[d]; } return -1; } int ask_num(node *p, int k) { while(p != null) { int l = p -> ch[0] -> sz + 1; int r = p -> ch[0] -> sz + p -> cnt; if(l <= k && k <= r) return p -> v; if(k > r) k -= r, p = p -> ch[1]; else p = p -> ch[0]; } } int ask_pre(node *p, int x) { int ans = 0; while(p != null) { if(p -> v < x) ans = p -> v, p = p -> ch[1]; else p = p -> ch[0]; } return ans; } int ask_suf(node *p, int x) { int ans = 0; while(p != null) { if(p -> v > x) ans = p -> v, p = p -> ch[0]; else p = p -> ch[1]; } return ans; } void init() { null = newnode(-INF, null); null -> sz = null -> cnt = 0; root = null; } int main() { init(); int n; scanf("%d", &n); while(n--) { int op, x; scanf("%d%d", &op, &x); switch(op) { case 1 : insert(root, x); break; case 2 : erase(root, x); break; case 3 : printf("%d\n", ask_rank(root, x)); break; case 4 : printf("%d\n", ask_num(root, x)); break; case 5 : printf("%d\n", ask_pre(root, x)); break; case 6 : printf("%d\n", ask_suf(root, x)); break; } } return 0; }转载于:https://www.cnblogs.com/Loi-Vampire/p/6017061.html
