题目描述
您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：
-
插入x数
-
删除x数(若有多个相同的数，因只删除一个)
-
查询x数的排名(排名定义为比当前数小的数的个数+1。若有多个相同的数，因输出最小的排名)
-
查询排名为x的数
-
求x的前驱(前驱定义为小于x，且最大的数)
- 求x的后继(后继定义为大于x，且最小的数)
输入输出格式
输入格式：
第一行为n，表示操作的个数,下面n行每行有两个数opt和x，opt表示操作的序号( 1 leq opt leq 61≤opt≤6 )
输出格式：
对于操作3,4,5,6每行输出一个数，表示对应答案
输入输出样例
输入样例#1： 复制
10 1 106465 4 1 1 317721 1 460929 1 644985 1 84185 1 89851 6 81968 1 492737 5 493598
输出样例#1： 复制
106465 84185 492737
说明
时空限制：1000ms,128M
1.n的数据范围： n leq 100000n≤100000
2.每个数的数据范围： [-{10}^7, {10}^7][−107,107]
来源：Tyvj1728 原名：普通平衡树
在此鸣谢
#include<iostream> #include<cstdio> #include<cmath> #include<algorithm> using namespace std; const int N = 1e5+5; const int INF = 599518803; int n, opt, x; struct NODE { NODE *fa; NODE *son[2]; int siz; int num, cnt; }node[N]; typedef NODE* Tree; Tree Root, now_node, null; inline void init() { Root = now_node = null = node; null->son[0] = null->son[1] = null; } inline int read() { char c = getchar(); int num = 0, f = 1; for(; !isdigit(c); c = getchar()) f = c == '-' ? -1 : f; for(; isdigit(c); c = getchar()) num = num * 10 + c - '0'; return num * f; } inline Tree new_node(int num, Tree fa) { ++ now_node; now_node->siz = 1; now_node->num = num; now_node->fa = fa; now_node->son[0] = now_node->son[1] = null; return now_node; } inline bool getgx(Tree root) { return root->fa->son[1] == root; } inline void connect(Tree root, Tree fa, bool flag) { if(fa != null) fa->son[flag] = root; else Root = root; root->fa = fa; } inline void update(Tree root) { root->siz = root->son[0]->siz + root->son[1]->siz + root->cnt; } inline void rotate(Tree root) { Tree fa = root->fa; bool a = getgx(root), b = !a; connect(root->son[b], fa, a); connect(root, fa -> fa, getgx(fa)); connect(fa, root, b); update(fa); update(root); if(root->fa == null) Root = root; } inline void splay(Tree root, Tree goal) { for(; root->fa != goal; rotate(root)) if(root->fa->fa != goal) rotate(getgx(root) == getgx(root->fa) ? root->fa : root); } void insert(int num) { if(Root == null) { Root = new_node(num, null); Root->cnt = 1; } else { Tree root = Root; for(; root->num != num; root = root->son[num > root->num]) { ++ (root->siz); if(root->son[num > root->num] == null) root->son[num > root->num] = new_node(num, root); } ++ (root->cnt); splay(root, null); } } void erase(int num) { if(Root == null) return; else { Tree root = Root; for(;root != null && root->num != num; root = root->son[num > root->num]); if(root == null) return; splay(root, null); -- (root->cnt); if(!root->cnt) { if(root->son[0] != null) { Tree tmp = root->son[0]; for(;tmp->son[1] != null; tmp = tmp->son[1]); splay(tmp, null); Root->son[1] = root->son[1]; if(Root->son[1] != null) Root->son[1]->fa = Root; } else { Root = root->son[1]; Root->fa = null; } } } } inline int query_rank(int num) { int rank = 0; for(Tree root = Root; root != null; root = root->son[num > root->num]) { if(num == root->num) return rank + root->son[0]->siz + 1; if(num > root->num) rank += root->son[0]->siz + root->cnt; } return rank; } inline int query_num(int rank) { for(Tree root = Root; root != null; ) { if(rank <= root->son[0]->siz) root = root->son[0]; else if(rank > root->son[0]->siz + root->cnt) rank -= root->son[0]->siz + root->cnt, root = root->son[1]; else return root->num; } } inline int query_pre(int x) { int pre = -INF; for(Tree root = Root; root != null; root = root->son[x > root->num]) { if(x > root->num) pre = max(pre, root->num); } return pre; } inline int query_nxt(int x) { int nxt = INF; for(Tree root = Root; root != null; root = root->son[x >= root->num]) { if(root->num > x) nxt = min(nxt, root->num); } return nxt; } int main() { init(); n = read(); for(int i = 1; i <= n; ++ i) { opt = read(), x = read(); switch(opt) { case 1: insert(x); break; case 2: erase(x); break; case 3: printf("%d ", query_rank(x)); break; case 4: printf("%d ", query_num(x)); break; case 5: printf("%d ", query_pre(x)); break; default: printf("%d ", query_nxt(x)); } } return 0; }