【模板】普通平衡树
题目描述
您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：
- 插入x数
- 删除x数(若有多个相同的数，因只删除一个)
- 查询x数的排名(排名定义为比当前数小的数的个数+1。若有多个相同的数，因输出最小的排名)
- 查询排名为x的数
- 求x的前驱(前驱定义为小于x，且最大的数)
- 求x的后继(后继定义为大于x，且最小的数)
输入格式
第一行为nn，表示操作的个数,下面nn行每行有两个数opt和x，opt表示操作的序号(1≤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
分析：
当初做这题时我内心是崩溃的。。。（不过最近又敲一遍快多了，2个小时左右吧）
CODE:
1 #include<bits/stdc++.h> 2 using namespace std; 3 int root,size,m,ans; 4 struct aaa{ 5 int l,r; 6 int size; 7 int weight; 8 int fix; 9 int val; 10 }tree[1000000]; 11 void update(int k){ 12 tree[k].size=tree[tree[k].l].size+tree[tree[k].r].size+tree[k].weight; 13 return; 14 } 15 void left_turn(int &k){ 16 int rson=tree[k].r; 17 tree[k].r=tree[rson].l; 18 tree[rson].l=k; 19 tree[rson].size=tree[k].size; 20 update(k); 21 k=rson; 22 } 23 void right_turn(int &k){ 24 int lson=tree[k].l; 25 tree[k].l=tree[lson].r; 26 tree[lson].r=k; 27 tree[lson].size=tree[k].size; 28 update(k); 29 k=lson; 30 } 31 void insert(int &k,int x){ 32 if(k==0){ 33 size++; 34 k=size; 35 tree[k].size=1; 36 tree[k].weight=1; 37 tree[k].val=x; 38 tree[k].fix=rand(); 39 return; 40 } 41 tree[k].size++; 42 if(tree[k].val==x){ 43 tree[k].weight++; 44 return; 45 } 46 if(tree[k].val<x){ 47 insert(tree[k].r,x); 48 if(tree[tree[k].r].fix<tree[k].fix) 49 left_turn(k); 50 } 51 if(tree[k].val>x){ 52 insert(tree[k].l, x); 53 if(tree[tree[k].l].fix<tree[k].fix) 54 right_turn(k); 55 } 56 } 57 void del(int &k,int x){ 58 if(tree[k].val==x){ 59 if(tree[k].weight>1){ 60 tree[k].weight--; 61 tree[k].size--; 62 return; 63 } 64 if(tree[k].l*tree[k].r==0) 65 k=tree[k].l+tree[k].r; 66 else 67 if(tree[tree[k].l].fix<tree[tree[k].r].fix) 68 right_turn(k),del(k,x); 69 else 70 left_turn(k),del(k,x); 71 } 72 else 73 if(tree[k].val>x) 74 tree[k].size--,del(tree[k].l,x); 75 else 76 tree[k].size--,del(tree[k].r,x); 77 } 78 int find1(int &k,int x){ 79 if(k==0) return 0; 80 if(tree[k].val==x) return tree[tree[k].l].size+1; 81 if(tree[k].val<x) return tree[tree[k].l].size+tree[k].weight+find1(tree[k].r,x); 82 if(tree[k].val>x) return find1(tree[k].l,x); 83 } 84 int find2(int &k,int x){ 85 if(x<=tree[tree[k].l].size) 86 return find2(tree[k].l,x); 87 if(x>tree[tree[k].l].size+tree[k].weight) 88 return find2(tree[k].r,x-tree[tree[k].l].size-tree[k].weight); 89 return tree[k].val; 90 } 91 void min_max(int &k,int x){ 92 if(k==0) return; 93 if(tree[k].val<x) 94 ans=k,min_max(tree[k].r,x); 95 else min_max(tree[k].l,x); 96 } 97 void max_min(int &k,int x){ 98 if(k==0) return; 99 if(tree[k].val>x) 100 ans=k,max_min(tree[k].l,x); 101 else max_min(tree[k].r,x); 102 } 103 int main(){ 104 int f,x; 105 scanf("%d",&m); 106 for (int i=1;i<=m;++i){ 107 scanf("%d%d",&f,&x); 108 ans=0; 109 if (f==1) insert(root,x); 110 if (f==2) del(root,x); 111 if (f==3) printf("%d\n",find1(root,x)); 112 if (f==4) printf("%d\n",find2(root,x)); 113 if (f==5) {min_max(root,x); printf("%d\n",tree[ans].val);} 114 if (f==6) {max_min(root,x); printf("%d\n",tree[ans].val);} 115 } 116 return 0; 117 }
优质内容筛选与推荐>>
1、JavaScript
2、数据库学习 ORA-12545:因目标主机或对象不存在，连接失败
3、我在改变！
4、Java实现多线程的两种方式
5、android textview 设置text 字体