您需要写一种数据结构（可参考题目标题），来维护一些数，其中需要提供以下操作：
-
插入x数
-
删除x数(若有多个相同的数，因只删除一个)
-
查询x数的排名(若有多个相同的数，因输出最小的排名)
-
查询排名为x的数
-
求x的前驱(前驱定义为小于x，且最大的数)
- 求x的后继(后继定义为大于x，且最小的数)
--by 洛谷；
http://www.lydsy.com/JudgeOnline/problem.php?id=3224
话说，没时间写题解啊——
不过，也就是个平衡树的模板题；
就存下代码吧
treap哟；
好像很少见写treap的，但常数还是挺小的orz；
哎，最近怎么老写模板啊？
代码如下：
1 #include<cstdio> 2 #include<cstdlib> 3 using namespace std; 4 #define INF 2147483647 5 int n; 6 struct poo 7 { 8 int size,value,key,cnt; 9 int ch[2]; 10 }data[100001]; 11 int tot,root,x; 12 int make_data(int ); 13 void insert(int&); 14 void roll(int&); 15 int find( ); 16 int rank( ); 17 void del(int&); 18 int las(int ); 19 int nex(int ); 20 void up(int ); 21 int main() 22 { 23 int i,j; 24 data[0].value=INF;data[0].key=INF; 25 scanf("%d",&n); 26 for(i=1;i<=n;i++){ 27 scanf("%d%d",&j,&x); 28 switch(j){ 29 case 1:insert(root);break; 30 case 2: del(root);break; 31 case 3: printf("%d ",rank( ));break; 32 case 4: printf("%d ",find( ));break; 33 case 5: printf("%d ", las(root));break; 34 case 6: printf("%d ", nex(root));break; 35 } 36 } 37 } 38 int make_data(int value) 39 { 40 tot++; 41 data[tot].cnt++; 42 data[tot].key=(rand()/2+rand()/2); 43 data[tot].size=1; 44 data[tot].value=value; 45 return tot; 46 } 47 void insert(int &now) 48 { 49 if(now==0){ 50 now=make_data(x); 51 return; 52 } 53 if(data[now].value==x){ 54 data[now].cnt++; 55 data[now].size++; 56 } 57 else{ 58 int wh=x < data[now].value ? 0 : 1; 59 insert(data[now].ch[wh]); 60 if(data[now].key>=data[data[now].ch[wh]].key) 61 roll(now); 62 } 63 up(now); 64 } 65 void roll(int &now) 66 { 67 int wh=data[data[now].ch[0]].key<data[data[now].ch[1]].key?0:1; 68 int son=data[now].ch[wh]; 69 data[now].ch[wh]=data[son].ch[wh^1]; 70 data[son].ch[wh^1]=now; 71 up(now); 72 now=son; 73 } 74 int find() 75 { 76 int now=root; 77 int ls,rs; 78 ls=data[now].ch[0];rs=data[now].ch[1]; 79 while(x<=data[ls].size||x>data[now].size-data[rs].size){ 80 if(data[ls].size>=x) 81 now=ls; 82 else{ 83 x=x+data[rs].size-data[now].size; 84 now=rs; 85 } 86 ls=data[now].ch[0];rs=data[now].ch[1]; 87 } 88 return data[now].value; 89 } 90 int rank() 91 { 92 int now=root,ans=0; 93 int ls=data[now].ch[0],rs=data[now].ch[1]; 94 while(x!=data[now].value&&x!=0) 95 { 96 if(x<data[now].value) 97 now=ls; 98 else{ 99 ans+=data[now].size-data[rs].size; 100 now=rs; 101 } 102 ls=data[now].ch[0];rs=data[now].ch[1]; 103 } 104 return ans+data[ls].size+1; 105 } 106 void del(int &now) 107 { 108 if(data[now].value==x){ 109 if(data[now].cnt==1){ 110 if(data[now].ch[0]*data[now].ch[1]==0){ 111 now=data[now].ch[1]+data[now].ch[0]; 112 return ; 113 } 114 roll(now); 115 int wh=data[data[now].ch[0]].value==x?0:1; 116 del(data[now].ch[wh]); 117 } 118 else{ 119 data[now].size--; data[now].cnt--; 120 } 121 } 122 else{ 123 int wh=data[now].value>x?0:1; 124 del(data[now].ch[wh]); 125 } 126 up(now); 127 } 128 int las(int now) 129 { 130 int ans=0,an=0; 131 if(!now)return 0; 132 if(data[now].value<x){ 133 ans=data[now].value; 134 an=las(data[now].ch[1]); 135 ans=an!=0?an:ans; 136 } 137 else{ 138 ans=las(data[now].ch[0]); 139 } 140 return ans; 141 } 142 int nex(int now) 143 { 144 int ans=0,an=0; 145 if(!now)return 0; 146 if(data[now].value>x){ 147 ans=data[now].value; 148 an=nex(data[now].ch[0]); 149 ans=an!=0?an:ans; 150 } 151 else{ 152 ans=nex(data[now].ch[1]); 153 } 154 return ans; 155 } 156 void up(int now) 157 { 158 data[now].size=data[data[now].ch[0]].size+data[data[now].ch[1]].size+data[now].cnt; 159 } 160 //treap on the 2017.1.21 161 //10 162 //1 5 163 //4 1 164 //1 6 165 //1 7 166 //1 10 167 //1 3 168 //1 4 169 //6 2 170 //1 8 171 //5 9 172 // 173 //14 174 //1 5 175 //1 6 176 //1 7 177 //1 10 178 //1 3 179 //1 4 180 //1 8 181 //3 3 182 //3 4 183 //3 5 184 //3 6 185 //4 5 186 //4 6 187 //4 7
祝AC哟；