struct Treap {
struct node {
node *son[];
int key,siz,wei,cnt;
node(int _key,node *f) {
son[]=son[]=f;
key=_key;siz=cnt=;wei=rand();
}
void pushup() {
siz=son[]->siz+son[]->siz+cnt;
}
}*null,*root;
Treap() {
null=new node(,);
null->siz=null->siz=;
null->wei=inf;root=null;// INF视情况而定
}
void rot(node* &rt,bool d) {
node* c=rt->son[!d];rt->son[!d]=c->son[d];
c->son[d]=rt;rt->pushup();c->pushup();rt=c;
}
void insert(const int &key,node* &rt) {
if (rt==null) {
rt=new node(key,null);return ;
}
if (key==rt->key) {
rt->cnt++;rt->siz++;return ;
}
bool d=key>rt->key;
insert(key,rt->son[d]);
if (rt->wei>rt->son[d]->wei) rot(rt,!d);
rt->pushup();
}
void remove(const int &key,node* &rt) {
if (rt==null) return ;
bool d=key>rt->key;
if (key==rt->key) {
if (rt->cnt>) {
rt->cnt--;rt->siz--;return ;
}
d=rt->son[]->wei>rt->son[]->wei;
if (rt->son[d]==null) {
delete rt;rt=null;return ;
}
rot(rt,!d);remove(key,rt->son[!d]);
} else remove(key,rt->son[d]);
rt->pushup();
}
node* select(int k,node* rt) {
int s=rt->son[]->siz+rt->cnt;
if (k>=rt->son[]->siz+&&k<=s) return rt;
if (s>k) return select(k,rt->son[]);
else return select(k-s,rt->son[]);
}
int rank(const int &key,node* rt) {
if (rt==null) return ;
int s=rt->son[]->siz+rt->cnt;
if (key==rt->key) return rt->son[]->siz+;
if (key<rt->key) return rank(key,rt->son[]);
else return s+rank(key,rt->son[]);
}
int pre(const int &k) {
node* t=root;int ret=;
while (t!=null)
if (t->key<k) ret=t->key,t=t->son[];
else t=t->son[];
return ret;
}
int sub(const int &k) {
node* t=root;int ret=;
while (t!=null)
if (t->key>k) ret=t->key,t=t->son[];
else t=t->son[];
return ret;
}
};