题目描述
您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：
-
插入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<cstring> #include<cmath> #include<algorithm> #include<ctime> using namespace std; const int N=1e6+5; const int INF=599518803; int n,opt,x; struct Node { Node *son[2]; //左右儿子 // int lson,rson; int key; //这个节点的输入的值 int key_cnt; //这个值出现的次数 int heap_key; //rand()的维护堆的性质的值 int size; //这棵树的节点个数 }node[N],_null; typedef Node* Tree; Tree node_now,root,null; int read() { char c=getchar();int num=0,f=1; for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) num=num*10+c-'0'; return num*f; } void init() { srand(time(NULL)); node_now=node; root=null=&_null; null->heap_key=null->key=2147483647; null->son[0]=null->son[1]=null; null->size=0; null->key_cnt=0; } Tree newNode(int key) { ++node_now; node_now->key=key; node_now->key_cnt=1; node_now->heap_key=rand(); node_now->size=1; node_now->son[0]=null; node_now->son[1]=null; return node_now; } void rotate(Tree &root,bool flag) { Tree tmp=root->son[!flag]; root->son[!flag]=tmp->son[flag]; tmp->son[flag]=root; root->size=root->son[0]->size+root->son[1]->size+root->key_cnt; tmp->size=tmp->son[0]->size+tmp->son[1]->size+tmp->key_cnt; root=tmp; } void insert(Tree &root,int key) { if(root==null) root=newNode(key); else if(root->key==key) ++root->key_cnt,++root->size; else { //printf(" %d ",root->key); ++root->size; bool flag=key>root->key; //WA点1：把root->key写成了root->heap_key, 粗心！ insert(root->son[flag],key); if(root->heap_key<root->son[flag]->heap_key) rotate(root,!flag); } } void erase(Tree &root,int key) { if(root==null) return; if(root->key!=key) { bool flag=key>root->key; --root->size; erase(root->son[flag],key); } else { if(root->key_cnt>1) --root->key_cnt, --root->size; else if(root->son[0]==null) root=root->son[1]; else if(root->son[1]==null) root=root->son[0]; else { bool flag=root->son[0]->heap_key>root->son[1]->heap_key; rotate(root,flag); erase(root,key); } } } int query_rank(Tree root,int x) { if(root==null) return 0; if(root->key==x) return root->son[0]->size+1; bool flag=x>root->key; if(flag) return root->son[0]->size+root->key_cnt+query_rank(root->son[1],x); else return query_rank(root->son[0],x); } int query_num(Tree root,int k) { if(root==null) return 0; else if(k<=root->son[0]->size) return query_num(root->son[0],k); else if(k>root->son[0]->size+root->key_cnt) return query_num(root->son[1],k-root->son[0]->size-root->key_cnt); else return root->key; } int query_pre(Tree root,int x) { if(root==null) return -2147483646; else if(root->key<x) return max(root->key,query_pre(root->son[1],x)); else return query_pre(root->son[0],x); } int query_nxt(Tree root,int x) { if(root==null) return 2147483647; //printf("%d ",root->key); else if(root->key>x) return min(root->key,query_nxt(root->son[0],x)); else return query_nxt(root->son[1],x); } int main() { //freopen("233.in","r",stdin); //freopen("233.out","w",stdout); init(); n=read(); while(n--) { opt=read(),x=read(); switch(opt) { case 1: insert(root,x);break; case 2: erase(root,x);break; case 3: printf("%d ",query_rank(root,x));break; case 4: printf("%d ",query_num(root,x));break; case 5: printf("%d ",query_pre(root,x));break; default: printf("%d ",query_nxt(root,x)); } } return 0; }