思路
非旋treap的思想是范浩强引入的，所以也被称为fhq treap。
主要操作为分裂和合并。
注释都在代码里了，基本每一行都有。
代码
/*
By Nero Claudius Caeser Augustus Germanicus,
Emperor of the Roman Empire.
*/
#include <bits/stdc++.h>
using namespace std;
namespace StandardIO{
template<typename T>void read(T &x){
x=0;T f=1;char c=getchar();
for(; c<'0'||c>'9'; c=getchar()) if(c=='-') f=-1;
for(; c>='0'&&c<='9'; c=getchar()) x=x*10+c-'0';
x*=f;
}
template<typename T>void write(T x){
if(x<0) putchar('-'),x*=-1;
if(x>=10) write(x/10);
putchar(x%10+'0');
}
} using namespace StandardIO;
namespace Project{
#define int long long
const int N=500005;
int n,op,v;
int tot,root;// 节点总数和根节点。
int ch[N][2],size[N],rnd[N],val[N]; // ch表示两个儿子，size表示子树（不包括自己）的大小，rnd表示随机权值，val表示节点储存值。
inline int newNode(int _v){++tot,val[tot]=_v,size[tot]=1,rnd[tot]=rand();return tot;} // newNode返回一个新节点的位置。
inline void pushup(int pos){size[pos]=size[ch[pos][0]]+size[ch[pos][1]]+1;} // pushup更新节点的大小。
int merge(int x,int y){ // merge把两个treap合并。 （我们假定y比x大）
if(!x||!y) return x+y; // 如果有不是都存在，直接返回就好了。
if(rnd[x]<rnd[y]){ // 根据随机权值决定谁做父亲，以此保证平衡性。
ch[x][1]=merge(ch[x][1],y); // 由于y的随机权值比较大，所以让它做儿子，滚到右边去。
pushup(x); // 更新大小。
return x; // 返回位置。
}else{ // 反之同理。
ch[y][0]=merge(x,ch[y][0]);
pushup(y);
return y;
}
}
void split(int now,int k,int &x,int &y){ // 把now树按照权值k分成两半，存入x和y里面。 当然也有按照size分裂的，但是此处不需要。
if(!now) x=y=0; // 废话。
else{
if(val[now]<=k) x=now,split(ch[now][1],k,ch[now][1],y); // 分裂点不在左子树中，所以分裂右子树。
else y=now,split(ch[now][0],k,x,ch[now][0]); // 反之。
pushup(now); // 更新大小。
}
}
int kth(int now,int k){ // 返回now树上的k小点。
while(1){
if(size[ch[now][0]]>=k) now=ch[now][0]; // 由于左子树大小比k大，所以肯定在左子树中。
else{
if(k==size[ch[now][0]]+1) return now; // 找到答案了，返回。
k-=size[ch[now][0]]+1,now=ch[now][1]; // 在右子树中。
}
}
}
void MAIN(){
srand((unsigned)time(NULL));
read(n);
while(n--){
read(op),read(v);
if(op==1){ // 插入操作。
int x,y;
split(root,v,x,y); // 把树按照v分裂。
root=merge(merge(x,newNode(v)),y); // 在原来的两半中间插入v，然后merge在一起，比较显然。
}else if(op==2){ // 删除操作。
int x,y,z;
split(root,v,x,z); // v其实在以v分裂的左半边的右边。
split(x,v-1,x,y);
y=merge(ch[y][0],ch[y][1]); // 把v给丢掉。
root=merge(merge(x,y),z);
}else if(op==3){ // 查询排名。
int x,y;
split(root,v-1,x,y); // 按v分裂，这样可以得到比自己小的数的个数。
write(size[x]+1),putchar('\n');
root=merge(x,y);
}else if(op==4){ // 查询排名为x的数。
write(val[kth(root,v)]),putchar('\n'); // 略。。
}else if(op==5){ // 求前驱。
int x,y;
split(root,v-1,x,y); // 原理参考删除操作。
write(val[kth(x,size[x])]),putchar('\n');
root=merge(x,y);
}else{ // 求后继。
int x,y;
split(root,v,x,y); // 略
write(val[kth(y,1)]),putchar('\n');
root=merge(x,y);
}
}
}
#undef int
}
int main(){
// freopen(".in","r",stdin);
// freopen(".out","w",stdout);
Project::MAIN();
}