第一个平衡树板子，有旋Treap。用随机函数规定一个堆，维护点权的同时维护堆的性质，可以有效地避免退化成链。按我的理解，建立一棵二叉排序树，树的形态会和给出节点的顺序有关。按照出题人很机智定理，数据肯定不会太容易操作，这时候就需要我们自行调整“数据顺序”，平衡树应运而生。
这个板子涵盖的操作有左旋、右旋(维护堆性质)、添加节点、删除节点(建树相关)、查找第x个元素、查找元素排名、查找前驱、查找后继这8种操作。改变树本身的操作都是取地址传参的，询问操作则都是简单传参。原理不是太难理解，应用则看以后刷题了。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<ctime>
#include<cstdlib>
using namespace std;
const int sj=;
int n,opt,g,jg,cs,size;
struct tree
{
int l,r,v,w,rnd,size;
}t[sj];
void update(int x)
{
t[x].size=t[t[x].l].size+t[t[x].r].size+t[x].w;
}
void lturn(int &x)
{
int tt=t[x].r;
t[x].r=t[tt].l;
t[tt].l=x;
t[tt].size=t[x].size;
update(x);
x=tt;
}
void rturn(int &x)
{
int tt=t[x].l;
t[x].l=t[tt].r;
t[tt].r=x;
t[tt].size=t[x].size;
update(x);
x=tt;
}
void cr(int &x,int y)
{
if(x==)
{
size++;
x=size;
t[x].size=t[x].w=;
t[x].v=y;
t[x].rnd=rand();
return;
}
t[x].size++;
if(t[x].v==y) t[x].w++;
else if(y>t[x].v)
{
cr(t[x].r,y);
if(t[t[x].r].rnd<t[x].rnd) lturn(x);
}
else
{
cr(t[x].l,y);
if(t[t[x].l].rnd<t[x].rnd) rturn(x);
}
}
void sc(int &k,int x)
{
if(k==) return;
if(t[k].v==x)
{
if(t[k].w>)
{
t[k].w--;
t[k].size--;
return;
}
if(t[k].l*t[k].r==) k=t[k].l+t[k].r;
else if(t[t[k].l].rnd<t[t[k].r].rnd)
rturn(k),sc(k,x);
else
lturn(k),sc(k,x);
}
else if(x>t[k].v)
t[k].size--,sc(t[k].r,x);
else
t[k].size--,sc(t[k].l,x);
}
int query_rank(int k,int x)
{
if(k==) return ;
if(t[k].v==x) return t[t[k].l].size+;
else if(x>t[k].v)
return t[t[k].l].size+t[k].w+query_rank(t[k].r,x);
else return query_rank(t[k].l,x);
}
int query_num(int k,int x)
{
if(k==) return ;
if(x<=t[t[k].l].size)
return query_num(t[k].l,x);
else if(x>t[t[k].l].size+t[k].w)
return query_num(t[k].r,x-t[t[k].l].size-t[k].w);
else return t[k].v;
}
void query_pre(int k,int x)
{
if(k==) return;
if(t[k].v<x)
jg=k,query_pre(t[k].r,x);
else query_pre(t[k].l,x);
}
void query_sub(int k,int x)
{
if(k==) return;
if(t[k].v>x)
jg=k,query_sub(t[k].l,x);
else query_sub(t[k].r,x);
}
int main()
{
//freopen("t.txt","r",stdin);
scanf("%d",&n);
for(int i=;i<=n;i++)
{
scanf("%d%d",&opt,&cs);
if(opt==)
cr(g,cs);
if(opt==)
sc(g,cs);
if(opt==)
printf("%d\n",query_rank(g,cs));
if(opt==)
printf("%d\n",query_num(g,cs));
if(opt==)
{
jg=;
query_pre(g,cs);
printf("%d\n",t[jg].v);
}
if(opt==)
{
jg=;
query_sub(g,cs);
printf("%d\n",t[jg].v);
}
}
//while(1);
return ;
}