学习了下treap
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
const int inf=<<;
int n,mn,root,delta,tot,ans;
int size[],child[][],cnt[],key[],p[];
void update(int x)
{
size[x]=size[child[x][]]+size[child[x][]]+cnt[x];
}
void rotate(int&x,int t)
{
int y=child[x][t];
child[x][t]=child[y][-t];
child[y][-t]=x;
update(x);
update(y);
x=y;
}
void insert(int&x,int k)
{
if(x)
{
if(key[x]==k) cnt[x]++;
else
{
int t=key[x]<k;
insert(child[x][t],k);
if(p[x]<p[child[x][t]]) rotate(x,t);
}
}
else
{
++tot;
x=tot;
p[x]=rand();
// printf("%d\n",p[x]);
key[x]=k;
cnt[x]=;
}
update(x);
}
void erase(int&x,int k)
{
if(key[x]==k)
{
if(cnt[x]>)
{
cnt[x]--;
update(x);
return;
}
if(!child[x][]&&!child[x][])
{
x=;
return;
}
int t=p[child[x][]]>p[child[x][]];
rotate(x,t);
erase(child[x][t^],k);
} else erase(child[x][key[x]<k],k);
update(x);
}
int find(int x,int k)
{
if(k<=size[child[x][]])
return find(child[x][],k);
k-=size[child[x][]]+cnt[x];
if(k<=) return key[x];
return find(child[x][],k);
}
int findrank(int x,int k)
{
if(key[x]==k) return size[child[x][]]+;
if(key[x]<k) return findrank(child[x][],k)+cnt[x]+size[child[x][]];
if(key[x]>k) return findrank(child[x][],k);
}
void findpro(int x,int k)
{
if(x==) return;
if(key[x]<k)
{
ans=key[x];
findpro(child[x][],k);
} else findpro(child[x][],k);
}
void findnxt(int x,int k)
{
if(x==) return;
if(key[x]>k)
{
ans=key[x];
findnxt(child[x][],k);
} else findnxt(child[x][],k);
}
int main()
{
p[]=-inf;
scanf("%d",&n);
while(n--)
{
int opt,a; scanf("%d%d",&opt,&a);
// printf("----------\nopt=%d\n",opt);
if(opt==) insert(root,a);
if(opt==) erase(root,a);
if(opt==) printf("%d\n",findrank(root,a));
if(opt==) printf("%d\n",find(root,a));
if(opt==) {findpro(root,a);printf("%d\n",ans);ans=;}
if(opt==) {findnxt(root,a);printf("%d\n",ans);ans=;}
// printf("----------\n");
}
return ;
}