fhq-Treap

split(p, pL ,pR, x) 将 二叉树 p 分裂成2棵树 pL 和 pR ，其中 pL 包含所有<=x的结点，pR 包含剩下的节点。
merge(p, pL, pR) 将 二叉树 pL 和 pR 重新合并成一棵树 p，注意此处要求 pL 和 pR 的值域是不重叠（没有交叉）的。
其他的rank(),kth(),prev(),next()函数和BST一样。

#include<bits/stdc++.h>
using namespace std;
int n;
const int N = 1e5+10;
struct node{
    int val,key;
    int l,r;
    int siz;
}fhq[N];
int root,cnt;
int newnode(int val){
    fhq[++cnt].val = val;
    fhq[cnt].key = rand();
    fhq[cnt].siz = 1;
    return cnt;
}
void update(int now){
    fhq[now].siz = fhq[fhq[now].l].siz+fhq[fhq[now].r].siz+1;
}
void split(int now,int val,int &x,int &y){
     if(!now) x=y=0;
    else 
    {
        if(fhq[now].val<=val)
        {
            x=now;
            split(fhq[now].r,val,fhq[now].r,y);
        }
        else 
        {
            y=now;
            split(fhq[now].l,val,x,fhq[now].l);
        }
        update(now);
    }
}
int merge(int x,int y){
    if(!x || !y) return x+y;
    if(fhq[x].key>fhq[y].key){
        fhq[x].r = merge(fhq[x].r,y);
        update(x);
        return x;
    }else{
        fhq[y].l = merge(x,fhq[y].l);
        update(y);
        return y;
    }
}
int x,y,z;
void insert(int val){
    split(root,val,x,y);
    root = merge(merge(x,newnode(val)),y);
}
void del(int val){
    split(root,val,x,z);
    split(x,val-1,x,y);
    y = merge(fhq[y].l,fhq[y].r);
    root = merge(merge(x,y),z);
}
void getrank(int val){
    split(root,val-1,x,y);
    printf("%d\n",fhq[x].siz+1);
    root = merge(x,y);
}
void getnum(int rank){
    int now = root;
    while(now){
        if(fhq[fhq[now].l].siz + 1 == rank) break;
        else if(fhq[fhq[now].l].siz>=rank) now = fhq[now].l;
        else{
            rank -= fhq[fhq[now].l].siz+1;
            now = fhq[now].r;
        }
    }
    printf("%d\n",fhq[now].val);
}
void prev(int val){
    split(root,val-1,x,y);
    int now = x;
    while(fhq[now].r) now = fhq[now].r;
    printf("%d\n",fhq[now].val);
    root = merge(x,y);
}
void next(int val){
    split(root,val,x,y);
    int now = y;
    while(fhq[now].l) now = fhq[now].l;
    printf("%d\n",fhq[now].val);
    root = merge(x,y);
}
int main(){
    cin>>n;
    int op,x;
    while(n--){
        cin>>op>>x;
        if(op == 1){
            insert(x);
        }else if(op == 2){
            del(x);
        }else if(op == 3){
            getrank(x);
        }else if(op == 4){
            getnum(x);
        }else if(op == 5){
            prev(x);
        }else{
            next(x);
        }
    }
    return 0;
}

以及一个pbds的题解，只能说pbds真的挺好用的

#include<cstdio>
#include<iostream>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long ll;
tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update> bbt;
int n;ll k,ans;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
} 
int main(){
    n=read();
    for(int i=1,opt;i<=n;i++){
        opt=read();k=read();
        if(opt==1) bbt.insert((k<<20)+i);
        if(opt==2) bbt.erase(bbt.lower_bound(k<<20));
        if(opt==3) printf("%d\n",bbt.order_of_key(k<<20)+1);
        if(opt==4) ans=*bbt.find_by_order(k-1),printf("%lld\n",ans>>20);
        if(opt==5) ans=*--bbt.lower_bound(k<<20),printf("%lld\n",ans>>20);
        if(opt==6) ans=*bbt.upper_bound((k<<20)+n),printf("%lld\n",ans>>20);
    }
    return 0;
}

下面是其中的一些含义

define pii pair[HTML_REMOVED]

define mp(x,y) make_pair(x,y)

tree[HTML_REMOVED],rb_tree_tag,tree_order_statistics_node_update> tr;
pii //存储的类型
null_type //无映射(低版本g++为null_mapped_type)
less[HTML_REMOVED] //从小到大排序
rb_tree_tag //红黑树
tree_order_statistics_node_update //更新方式
tr.insert(mp(x,y)); //插入;
tr.erase(mp(x,y)); //删除;
tr.order_of_key(pii(x,y)); //求排名
tr.find_by_order(x); //找k小值，返回迭代器
tr.join(b); //将b并入tr，前提是两棵树类型一样且没有重复元素
tr.split(v,b); //分裂，key小于等于v的元素属于tr，其余的属于b
tr.lower_bound(x); //返回第一个大于等于x的元素的迭代器
tr.upper_bound(x); //返回第一个大于x的元素的迭代器
//以上所有操作的时间复杂度均为O(logn)