话说天下大事，就像fhq treap —— 分久必合，合久必分
简单讲一讲。非旋treap主要依靠分裂和合并来实现操作。（递归，不维护fa不维护cnt）
合并的前提是两棵树的权值满足一边的最大的比另一边最小的还小。因此时合并时只需要维护键值的堆性质即可。这样每一次比较根节点，如果x比y小那么y直接接到x的右子树即可（需要满足权值的平衡树性质）；否则的话只需要反过来，把x接到y的左子树上。merge函数返回的值应当是合并完后的根节点。
分裂分为两种，排名和权值。然而我认为它们本质上是一样的。对于权值的分裂，对于每一个子树的根节点，若根节点比给定值a小，那么此节点及左子树一定比a小，归入x。否则此节点及右子树归入y。然后再递归操作还没有分类的那一个子树就好了。代码实现中的引用用的非常巧妙。可以把这里的引用理解为是需要修改的东西，利用递归的过程对其作出修改。
合并看键值，分裂看权值。
$Merge$
int merge(int u, int v){
if(!u||!v) return u|v;
if(key[u] < key[v]){
ch[u][] = merge(ch[u][], v);
pushup(u);
return u;
}
else{
ch[v][] = merge(u, ch[v][]);
pushup(v);
return v;
}
}
$Split$
void split_a(int u, int a, int& x, int& y){
if(!u){ x = y = ; return; }
if(val[u] <= a){
x = u;
split_a(ch[u][], a, ch[u][], y);
}
else{
y = u;
split_a(ch[u][], a, x, ch[u][]);
}
pushup(u);
}
void split_k(int u, int k, int& x, int& y){
if(!u){ x = y = ; return; }
if(size[ch[u][]]+1 <= k){
x = u;
split_k(ch[u][], k-size[ch[u][]]-1, ch[u][], y);
}
else{
y = u;
split_k(ch[u][], k, x, ch[u][]);
}
pushup(u);
}
有了这两个操作，其他操作yy一下即可，非常简便。
当然，在查询k大排名或前驱后继时，完全可以用普通平衡树（如splay）的做法。因为它满足平衡树的性质。也就是傻乎乎的去logn的从根节点往下走。那么既然我们有了split，查询最大最小值应该很方便了。要尽量让代码精简啊！
My Code:
/*By DennyQi 2018*/
#include <cstdio>
#include <queue>
#include <cstring>
#include <algorithm>
#include <ctime>
#include <cstdlib>
using namespace std;
typedef long long ll;
const int MAXN = ;
const int INF = 0x3f3f3f3f;
inline int Max(const int a, const int b){ return (a > b) ? a : b; }
inline int Min(const int a, const int b){ return (a < b) ? a : b; }
inline int read(){
int x = ; int w = ; register char c = getchar();
for(; c ^ '-' && (c < '' || c > ''); c = getchar());
if(c == '-') w = -, c = getchar();
for(; c >= '' && c <= ''; c = getchar()) x = (x<<) + (x<<) + c - ''; return x * w;
}
int N,opt,x,num_node,RooT;
int ch[MAXN][],val[MAXN],key[MAXN],size[MAXN];
inline void pushup(int x){
size[x] = size[ch[x][]] + size[ch[x][]] + ;
}
inline void clear(int x){
size[x]=val[x]=key[x]=ch[x][]=ch[x][]=;
}
int merge(int u, int v){
if(!u||!v) return u|v;
if(key[u] < key[v]){
ch[u][] = merge(ch[u][], v);
pushup(u);
return u;
}
else{
ch[v][] = merge(u, ch[v][]);
pushup(v);
return v;
}
}
void split_a(int u, int a, int& x, int& y){
if(!u){ x = y = ; return; }
if(val[u] <= a){
x = u;
split_a(ch[u][], a, ch[u][], y);
}
else{
y = u;
split_a(ch[u][], a, x, ch[u][]);
}
pushup(u);
}
void split_k(int u, int k, int& x, int& y){
if(!u){ x = y = ; return; }
if(size[ch[u][]]+ <= k){
x = u;
split_k(ch[u][], k-size[ch[u][]]-, ch[u][], y);
}
else{
y = u;
split_k(ch[u][], k, x, ch[u][]);
}
pushup(u);
}
inline void Insert(int v){//以v进行分裂，插入后合并。
val[++num_node]= v;
key[num_node] = rand();
size[num_node] = ;
int a,b;
split_a(RooT, v, a, b);
RooT = merge(merge(a,num_node), b);
}
inline void Delete(int v){//以v进行分裂，删除后合并。
int a,b,c,d;
split_a(RooT, v, a, b);
split_k(a, size[a]-, c, d);
clear(d);
RooT = merge(c, b);
}
inline int Rank(int v){//以v-1进行分裂，看左侧树的size
int a,b,ans;
split_a(RooT, v-, a, b);
ans = size[a]+;
RooT = merge(a, b);
return ans;
}
inline int Kth(int k){//以k进行分裂，依旧看左侧的size，但注意再分裂一次取出比k小的
int a,b,c,d,ans;
split_k(RooT, k, a, b);
split_k(a,size[a]-,c,d);
ans = val[d];
RooT = merge(merge(c,d),b);
return ans;
}
inline int Pre(int v){//与kth同理
int a,b,c,d,ans;
split_a(RooT, v-, a, b);
split_k(a,size[a]-,c,d);
ans = val[d];
RooT = merge(merge(c,d),b);
return ans;
}
inline int Nxt(int v){
int a,b,c,d,ans;
split_a(RooT, v, a, b);
split_k(b, , c, d);
ans = val[c];
RooT = merge(a,merge(c,d));
return ans;
}
void PrintTree(int u){
if(ch[u][]) PrintTree(ch[u][]);
printf("%d ",val[u]);
if(ch[u][]) PrintTree(ch[u][]);
}
int main(){
// freopen(".in","r",stdin);
srand((unsigned)time(NULL));
N = read();
while(N--){
opt = read(), x = read();
if(opt == ) Insert(x);
if(opt == ) Delete(x);
if(opt == ) printf("%d\n", Rank(x));
if(opt == ) printf("%d\n", Kth(x));
if(opt == ) printf("%d\n", Pre(x));
if(opt == ) printf("%d\n", Nxt(x));
}
return ;
}