真是太差了，到现在才打出一个平衡树的板子。。
感谢blackjack大佬提供的数组版treap板子！！基本完全照搬，blackjack太神啦！
但目前我只会这几个最基本的操作（说白了STL的(multi)set）也能干。。。
还差的好远-_-
#include<bits/stdc++.h>
#define L T[x].ls
#define R T[x].rs
using namespace std;
const int N=;
int root,sz,ans;
struct Node{
int val,sz,cnt,ls,rs,key;
}T[N];
void ref(int x){
T[x].sz=T[L].sz+T[R].sz+T[x].cnt;
}
void zig(int &x){
int y=R;
T[x].rs=T[y].ls;T[y].ls=x;
T[y].sz=T[x].sz;ref(x);ref(y);x=y;
}
void zag(int &x){
int y=L;
T[x].ls=T[y].rs;T[y].rs=x;
T[y].sz=T[x].sz;ref(x);ref(y);x=y;
}
void ins(int &x,int v){
if(!x){
x=++sz;
T[x]=(Node){v,,,,,rand()};
return;
}
if(T[x].val==v){
T[x].cnt++;T[x].sz++;
return;
}
T[x].sz++;
if(T[x].val<v){
ins(R,v);
if(T[R].key<T[x].key)
zig(x);
}
else{
ins(L,v);
if(T[L].key<T[x].key)
zag(x);
}
}
void del(int &x,int v){
if(!x)return;
if(T[x].val==v){
if(T[x].cnt>){
T[x].cnt--;T[x].sz--;
return;
}
if(!(L*R)){
x=L+R;return;
}
if(T[L].key<T[R].key)
zag(x),del(x,v);
else
zig(x),del(x,v);
}
else{
T[x].sz--;
if(T[x].val<v)del(R,v);
else del(L,v);
}
}
void pre(int x,int v){
if(!x)return;
if(T[x].val<v)
ans=x,pre(R,v);
else pre(L,v);
}
void nxt(int x,int v){
if(!x)return;
if(T[x].val>v)
ans=x,nxt(L,v);
else nxt(R,v);
}
int qnum(int x,int rk){
if(!x)return ;
if(rk<=T[L].sz)
return qnum(L,rk);
if(rk>T[L].sz+T[x].cnt)
return qnum(R,rk-T[L].sz-T[x].cnt);
return T[x].val;
}
int qrank(int x,int v){
if(!x)return ;
if(T[x].val==v)
return T[L].sz+;
if(T[x].val<v)
return qrank(R,v)+T[L].sz+T[x].cnt;
return qrank(L,v);
}
int main(){
int n;scanf("%d",&n);
while(n--){
int opt,t;scanf("%d%d",&opt,&t);
ans=;
switch(opt){
case :ins(root,t);break;
case :del(root,t);break;
case :ans=qrank(root,t);printf("%d\n",ans);break;
case :ans=qnum(root,t);printf("%d\n",ans);break;
case :pre(root,t);printf("%d\n",T[ans].val);break;
case :nxt(root,t);printf("%d\n",T[ans].val);break;
}
}
}