前言
您需要写一种数据结构，来维护一些数，其中需要提供一下的操作：
1.插入数值x
2.删除数值x（如果有多个，只删除一个）
3.查询数值x的排名（如有多个相同的数，应输出最小的排名）
4.查询排名为x的数值
5. 求数值x的前驱（小于x最大的数）
6.求数值x的后继（大于x最小的数）
首先我们引入一种数据结构叫二叉查找树（BST）。该树满足一下性质：
对于树的任意一个节点
1.该节点的关键码不小于它的左子树中任意节点的关键码
2.该节点的关键码不大于它的右子树中任意节点的关键码
通俗一点来讲就是，一个节点的左边都比他小，右边都比他大QWQ
显然，二叉查找树的中序遍历是一个单调递增的节点序列……
那么我们来考虑解决上面的普通平衡树（因为不是主角就不重点讲啦！！）
1.插入：从根节点开始访问，小了向左走，大了向右走，找不到就新建点啦
2.删除：同插入过程啦啦啦啦
3.查询排名：因为左子树的点都比此节点小，那抹排名就是左子树的size（大小）+1啦啦啦，求size应该都会吧……
4.查询数值：如果左子树的大小比要求排名大，就往左走，否则往右走，直到一样……
5.前驱：首先我们先找到这个数，因为左子树的点都比这个数小，所以向左儿子走一步，然后一直向右边走，走到头就是啦
6.后继：同理啦，向右儿子走一步，然后一直向左走
是不是感觉BST超简单的，没错就是这么简单……但是你没发现什么问题嘛？？
不不不
现在我按顺序插入1,2,3,4,5
树就变成了这样
我要是按顺序插入1,2,3……10^5
这特么不就变成链表了么
实际上就算不这么极端，也能分分钟把这种最单纯的2x查找树搞死
很显然这样是过不了普通平衡树的……
是不是感觉刚才看的都白看了，不不不，下面要将的treap就是基于2x进行优化的……
那么该怎么优化呢？？？
我们发现2x查找树的不足之处就在于它太深了（太深了……咳咳咳），因此我们就想减少它的深度，通俗的来讲就是把它拍扁。那么如何实现呢……
旋转（不转不是中国人……）
右旋，是让某个节点的左儿子站到自己原来的位置，然后自己成为原来左儿子的右儿子（左旋同理啦！！请自行脑补）可以看下面的动来动去的图
合理的旋转操作可以是BST变得更扁（you）平（xiu）。那么问题来了，怎么样才算合理呢？？？根据研究发现，在随机的数据下，普通的BST可以虐杀其他一切高级的树。Treap的思想就是利用“随机”来创造平衡的条件。因为在旋转的过程中必须维持BST的性质，所以Treap就把“随机”作用在堆性质上。
其实Treap就是Tree和Heap的合成词啦。Treap在插入每个新节点的时候，就给该节点随机生成一个额外的权值。然后像二叉堆的插入过程一样，自底向上依次检查，当某个节点不满足大根堆性质时，就执行单旋转，是该节点与其父节点的关系发生对换。
特别的，对于删除操作，因为Treap支持旋转，我们可以将要删除的节点转到叶子节点，然后直接删除，就可以避免信息更新的问题啦。
Treap的所有操作时间复杂度都是O（logn）的
下面附上丑丑的代码：
//By Bibi
/// .-~~~~~~~~~-._ _.-~~~~~~~~~-.
/// __.' ~. .~ `.__
/// .'// \./ \\`.
/// .'// | \\`.
/// .'// .-~"""""""~~~~-._ | _,-~~~~"""""""~-. \\`.
/// .'//.-" `-. | .-' "-.\\`.
/// .'//______.============-.. \ | / ..-============.______\\`.
/// .'______________________________\|/______________________________`.
#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=a;i<=b;++i)
#define dep(i,a,b) for(int i=a;i>=b;--i)
using namespace std;
const int MAXN=100010;
const int INF=0x7fffffff;
int read(){
int sum=0,flag=1;
char c;
for(;c<'0'||c>'9';c=getchar())if(c=='-') flag=-1;
for(;c>='0'&&c<='9';c=getchar())sum=(sum<<1)+(sum<<3)+c-'0';
return sum*flag;
}
int tot,root,n;
struct Treap{
int l,r;
int val,dat;
int cnt,size;
}tr[MAXN];
int New(int val){
tr[++tot].val=val;
tr[tot].dat=rand();
tr[tot].cnt=tr[tot].size=1;
return tot;
}
void update(int p){
tr[p].size=tr[tr[p].l].size+tr[tr[p].r].size+tr[p].cnt;
}
void build(){
New(-INF);New(INF);
root=1;tr[1].r=2;
update(root);
}
int getrankbyval(int p,int val){
if(!p) return 0;
if(tr[p].val==val) return tr[tr[p].l].size+1;
if(val<tr[p].val) return getrankbyval(tr[p].l,val);
return getrankbyval(tr[p].r,val)+tr[tr[p].l].size+tr[p].cnt;
}
int getvalbyrank(int p,int rank){
if(!p) return INF;
if(tr[tr[p].l].size>=rank) return getvalbyrank(tr[p].l,rank);
if(tr[tr[p].l].size+tr[p].cnt>=rank) return tr[p].val;
return getvalbyrank(tr[p].r,rank-tr[tr[p].l].size-tr[p].cnt);
}
void zig(int &p){
int q=tr[p].l;
tr[p].l=tr[q].r;tr[q].r=p;p=q;
update(tr[p].r);update(p);
}
void zag(int &p){
int q=tr[p].r;
tr[p].r=tr[q].l;tr[q].l=p;p=q;
update(tr[p].l);update(p);
}
void insert(int &p,int val){
if(!p) {p=New(val);return;}
if(val==tr[p].val) {tr[p].cnt++;update(p);return;}
if(val<tr[p].val){
insert(tr[p].l,val);
if(tr[p].dat<tr[tr[p].l].dat) zig(p);
}
else{
insert(tr[p].r,val);
if(tr[p].dat<tr[tr[p].r].dat) zag(p);
}
update(p);
}
int getpre(int val){
int ans=1;
int p=root;
while(p){
if(val==tr[p].val){
if(tr[p].l>0){
p=tr[p].l;
while(tr[p].r>0) p=tr[p].r;
ans=p;
}
break;
}
if(tr[p].val<val&&tr[p].val>tr[ans].val) ans=p;
p=val<tr[p].val ? tr[p].l:tr[p].r;
}
return tr[ans].val;
}
int getnext(int val){
int ans=2;
int p=root;
while(p){
if(val==tr[p].val){
if(tr[p].r){
p=tr[p].r;
while(tr[p].l) p=tr[p].l;
ans=p;
}
break;
}
if(tr[p].val>val&&tr[p].val<tr[ans].val) ans=p;
p=val<tr[p].val ? tr[p].l:tr[p].r;
}
return tr[ans].val;
}
void remove(int &p,int val){
if(!p) return;
if(val==tr[p].val){
if(tr[p].cnt>1) {tr[p].cnt--;update(p);return;}
if(tr[p].l||tr[p].r){
if(tr[p].r==0||tr[tr[p].l].dat>tr[tr[p].r].dat) zig(p),remove(tr[p].r,val);
else zag(p),remove(tr[p].l,val);
update(p);
}
else p=0;
return;
}
val<tr[p].val ? remove(tr[p].l,val):remove(tr[p].r,val);
update(p);
}
void init(){
n=read();
while(n--){
int opt=read(),x=read();
switch(opt){
case 1: insert(root,x);break;
case 2: remove(root,x);break;
case 3: printf("%d\n",getrankbyval(root,x)-1 );break;
case 4: printf("%d\n",getvalbyrank(root,x+1) );break;
case 5: printf("%d\n",getpre(x) );break;
case 6: printf("%d\n",getnext(x) );break;
}
}
}
int main(){
build();
init();
return 0;
}