本文版权归ljh2000和博客园共有，欢迎转载，但须保留此声明，并给出原文链接，谢谢合作。
本文作者：ljh2000
作者博客：http://www.cnblogs.com/ljh2000-jump/
转载请注明出处，侵权必究，保留最终解释权！
题目链接：BZOJ3224
正解：$Treap$
解题报告：
$Treap$其实就是二叉搜索树啦，加入了随机化权值之后可以保证树的形态比较平衡。
$Treap$既是一棵二叉搜索树又是一个大根堆（小根堆也行，随意啦），每次$insert$了之后给这个节点$rand$一个权值就好了，然后每次需要保证堆的性质，所以要维护一个向上旋转的操作。
这就是旋转式的$Treap$了，挺simple的。
//It is made by ljh2000
//有志者，事竟成，破釜沉舟，百二秦关终属楚；苦心人，天不负，卧薪尝胆，三千越甲可吞吴。
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#include <algorithm>
#include <ctime>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <string>
#include <complex>
#include <bitset>
using namespace std;
typedef long long LL;
typedef long double LB;
typedef complex<double> C;
const double pi = acos(-1);
const int MAXN = 100011;
int n,rt,tot,tr[MAXN][2],size[MAXN],r[MAXN],val[MAXN];
//维护按权值的二叉搜索树，同时是随机权值的大根堆
//相等的均靠左
inline void update(int x){ size[x]=size[tr[x][0]]+size[tr[x][1]]+1; }
inline int getint(){
int w=0,q=0; char c=getchar(); while((c<'0'||c>'9') && c!='-') c=getchar();
if(c=='-') q=1,c=getchar(); while (c>='0'&&c<='9') w=w*10+c-'0',c=getchar(); return q?-w:w;
}
inline void R(int &p,bool k){//把x的左/右儿子旋转上来
int t=tr[p][k]; tr[p][k]=tr[t][k^1]; tr[t][k^1]=p;
update(p); update(t); p=t;
}
inline void insert(int &p,int x){
if(!p) { p=++tot; val[p]=x; size[p]=1; r[p]=rand(); return ; }
size[p]++;//!!!
if(x<=val[p]) insert(tr[p][0],x); else insert(tr[p][1],x);
bool k=(x>val[p]);
if(r[ tr[p][k] ] > r[p]) R(p,k);//不满足大根堆性质，往上旋转
}
inline void out(int &p){//删除当前节点，不断旋转，直到没有左儿子或者没有右儿子就可以结束了
if(!tr[p][0] || !tr[p][1]) { p=tr[p][0]+tr[p][1]; return ; }
bool k=(r[ tr[p][1] ]>r[ tr[p][0] ]);//把key偏大的那个儿子旋转上来
R(p,k); size[p]--;//!!!
out(tr[p][k^1]);
}
inline void del(int &p,int k){//把当前子树中rank为k的结点删除
size[p]--;//!!!在最前面呀...
if(size[tr[p][0]]+1==k) { out(p); return ; }
if(size[tr[p][0]]>=k) del(tr[p][0],k);
else del(tr[p][1]/*!!!*/,k-size[tr[p][0]]-1);
}
inline int kth(int x,int k){//查询rank为k的数，rank最小的那个
while(x) {
if(size[tr[x][0]]+1==k) return val[x];
if(k<=size[tr[x][0]]) x=tr[x][0];
else k-=size[tr[x][0]]+1,x=tr[x][1];
}
return 0;
}
inline int rank(int x,int k){//查询>=k的第一个数的rank，最靠左的那个
int tot=1;
while(x) {
if(k<=val[x]) x=tr[x][0];
else tot+=size[tr[x][0]]+1,x=tr[x][1];
}
return tot;
}
inline void work(){
srand(23333);
n=getint(); int type,x;
while(n--) {
type=getint(); x=getint();
if(type==1) {
insert(rt,x);
}
else if(type==2) {
del(rt,rank(rt,x));
}
else if(type==3) {
printf("%d
",rank(rt,x));
}
else if(type==4) {
printf("%d
",kth(rt,x));
}
else if(type==5) {
printf("%d
", kth( rt, rank(rt,x)-1 ) );
}
else {
printf("%d
", kth( rt, rank(rt,x+1) ) );
}
}
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("3224.in","r",stdin);
freopen("3224.out","w",stdout);
#endif
work();
return 0;
}
//有志者，事竟成，破釜沉舟，百二秦关终属楚；苦心人，天不负，卧薪尝胆，三千越甲可吞吴。