http://www.lydsy.com/JudgeOnline/problem.php?id=3224 (题目链接)
题意
1. 插入x数；2. 删除x数(若有多个相同的数，因只删除一个)；3. 查询x数的排名(若有多个相同的数，因输出最小的排名)；4. 查询排名为x的数；5. 求x的前驱(前驱定义为小于x，且最大的数)；6. 求x的后继(后继定义为大于x，且最小的数)
Solution
treap板子。右转光勋总结→_→：平衡树
细节
一个节点还统计了这个数出现了几次，然后询问排名前驱后继什么的写的我蛋都要碎了T_T，所以这里旋转版的rank求的是小于$x$的数的个数，而不是$x$的排名。
旋转treap
// bzoj3224
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LL long long
#define inf 2147483640
#define Pi acos(-1.0)
#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout)
using namespace std; const int maxn=100010;
int n,sz,Dargen;
struct node {
int son[2],size,val,rnd,w;
int& operator [] (int x) {return son[x];}
}tr[maxn]; void pushup(int k) {
tr[k].size=tr[tr[k][0]].size+tr[tr[k][1]].size+tr[k].w;
}
void rotate(int &x,int p) { //记得&
int y=tr[x][p];
tr[x][p]=tr[y][p^1];tr[y][p^1]=x;x=y; //记得写x=y
pushup(tr[y][p^1]);pushup(y);
}
void insert(int &k,int x) {
if (!k) {tr[k=++sz].val=x;tr[k].rnd=rand();tr[k].size=tr[k].w=1;return;}
int p=x>tr[k].val;tr[k].size++;
if (tr[k].val==x) {tr[k].w++;return;}
insert(tr[k][p],x);
if (tr[tr[k][p]].rnd>tr[k].rnd) rotate(k,p);
}
void erase(int &k,int x) {
if (k==0) return;
if (tr[k].val==x) {
if (tr[k].w>1) {tr[k].w--;tr[k].size--;return;}
if (tr[k][0]*tr[k][1]==0) k=tr[k][0]+tr[k][1];
else rotate(k,tr[tr[k][0]].rnd<tr[tr[k][1]].rnd),erase(k,x);
}
else tr[k].size--,erase(tr[k][x>tr[k].val],x);
}
int find(int k,int x) {
if (!k) return 0;
if (tr[tr[k][0]].size<x && x<=tr[tr[k][0]].size+tr[k].w) return tr[k].val;
else if (x<=tr[tr[k][0]].size) return find(tr[k][0],x);
else return find(tr[k][1],x-tr[tr[k][0]].size-tr[k].w);
}
int rank(int k,int x) {
if (!k) return 0;
if (x<=tr[k].val) return rank(tr[k][0],x);
else return rank(tr[k][1],x)+tr[tr[k][0]].size+tr[k].w;
}
int main() {
scanf("%d",&n);
for (int op,x,i=1;i<=n;i++) {
scanf("%d%d",&op,&x);
if (op==1) insert(Dargen,x);
if (op==2) erase(Dargen,x);
if (op==3) printf("%d\n",rank(Dargen,x)+1);
if (op==4) printf("%d\n",find(Dargen,x));
if (op==5) printf("%d\n",find(Dargen,rank(Dargen,x)));
if (op==6) printf("%d\n",find(Dargen,rank(Dargen,x+1)+1));
}
return 0;
}
非旋转treap
// bzoj3224
#include<algorithm>
#include<iostream>
#include<cstdlib>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LL long long
#define inf 2147483640
#define Pi acos(-1.0)
#define free(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);
using namespace std; const int maxn=100010;
int n,sz,Dargen;
struct node {
int son[2],size,val,rnd;
int& operator [] (int x) {return son[x];}
}tr[maxn]; void pushup(int k) {
tr[k].size=tr[tr[k][0]].size+tr[tr[k][1]].size+1;
}
void split(int k,int x,int &a,int &b) {
if (!x) {a=0;b=k;return;}
int l=tr[k][0],r=tr[k][1];
if (tr[l].size==x) tr[k][0]=0,a=l,b=k;
else if (tr[l].size+1==x) tr[k][1]=0,a=k,b=r;
else if (x<tr[l].size) split(l,x,a,tr[k][0]),b=k;
else split(r,x-tr[l].size-1,tr[k][1],b),a=k;
pushup(k);
}
int merge(int x,int y) { //按顺序x<y
if (!x || !y) return x|y;
if (tr[x].rnd>tr[y].rnd) {
tr[x][1]=merge(tr[x][1],y);
pushup(x);return x;
}
else {
tr[y][0]=merge(x,tr[y][0]);
pushup(y);return y;
}
}
int rank(int k,int x) {
if (!k) return 1;
if (x<=tr[k].val) return rank(tr[k][0],x);
else return rank(tr[k][1],x)+tr[tr[k][0]].size+1;
}
int find(int k,int x) {
if (!k) return 0;
if (tr[tr[k][0]].size+1==x) return tr[k].val;
else if (x<=tr[tr[k][0]].size) return find(tr[k][0],x);
else return find(tr[k][1],x-tr[tr[k][0]].size-1);
}
void insert(int x) {
int l,r;
tr[++sz].val=x;tr[sz].rnd=rand();tr[sz].size=1;
split(Dargen,rank(Dargen,x)-1,l,r);
Dargen=merge(merge(l,sz),r);
}
void erase(int k) {
int x,y;
split(Dargen,k,x,y);
split(x,k-1,x,k);
Dargen=merge(x,y);
}
int main() {
scanf("%d",&n);
for (int op,x,i=1;i<=n;i++) {
scanf("%d%d",&op,&x);
if (op==1) insert(x);
if (op==2) erase(rank(Dargen,x));
if (op==3) printf("%d\n",rank(Dargen,x));
if (op==4) printf("%d\n",find(Dargen,x));
if (op==5) printf("%d\n",find(Dargen,rank(Dargen,x)-1));
if (op==6) printf("%d\n",find(Dargen,rank(Dargen,x+1)));
}
return 0;
}