Treap

树堆（英语：Treap），是有一个随机附加域满足堆的性质的二叉搜索树，其结构相当于以随机数据插入的二叉搜索树。相对于其他的平衡二叉搜索树，Treap的特点是实现简单，且能基本实现随机平衡的结构。

基本介绍:

梗概

$Treap=Tree+Heap$
$Treap$ 本身是一棵二叉搜索树，它的左子树和右子树也分别是一个 $Treap$ ，和一般的二叉搜索树不同的是， $Treap$ 记录一个额外的数据，就是优先级。 $Treap$ 在以关键码构成二叉搜索树的同时，还满足堆的性质。 $Treap$ 维护堆性质的方法用到了旋转，只需要两种旋转，编程复杂度比 $Splay$ 要小一些。

插入

给节点随机分配一个优先级，先和二叉搜索树的插入一样，先把要插入的点插入到一个叶子上，然后跟维护堆一样，如果当前节点的优先级比根大就旋转，如果当前节点是根的左儿子就右旋如果当前节点是根的右儿子就左旋。
由于旋转是 $O(1)$ 的，最多进行 $h$ 次（ $h$ 是树的高度），插入的复杂度是 $O(h)$ 的，在期望情况下 $O(log n)$，所以它的期望复杂度是 $O(log n)$

删除

因为 $Treap$ 满足堆性质，所以只需要把要删除的节点旋转到叶节点上，然后直接删除就可以了。具体的方法就是每次找到优先级最大的儿子，向与其相反的方向旋转，直到那个节点被旋转到了叶节点，然后直接删除。
删除最多进行 $O(h)$ 次旋转，期望复杂度是 $O(logn)$

查找

和一般的二叉搜索树一样，但是由于 $Treap$ 的随机化结构，$Treap$ 中查找的期望复杂度是 $O(logn)$

有空再补注释

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int N = 100009, INF = 1e9;
struct node
{
    int l, r;//当前节点的左右儿子的下标
    int num;//当前节点的值 
    int cnt;//当前节点的出现次数
    int size;//当前节点子树的大小
    int val;//随机值，用来维持平衡树的平衡 
} tr[N];//平衡树 

int T;//询问次数 
int root;//根节点的编号 
int now = 0;//当前平衡树的节点个数

void merge(int x)
{
    tr[x].size = tr[tr[x].l].size + tr[tr[x].r].size + tr[x].cnt;
    //tr[tr[x].l].size -> 左儿子个数
    //tr[tr[x].r].size -> 右儿子个数
    //tr[x].cnt -> 当前节点的个数 
    return;
}

int add(int x)//新建一个叶节点
//这里x传的是新的节点的值 
{
    now++;//节点数加1
    tr[now].l = tr[now].r = 0;//一开始没有儿子，所以赋值为0 
    tr[now].val = rand();//给val赋随机值 
    tr[now].num = x;//赋值
    tr[now].cnt = tr[now].size = 1;
    //新建节点时，默认为叶节点，所以节点个数为1，节点大小为1
    return now;
}

void build()//初始化平衡树 
{
    add(-INF), add(INF);
    root = 1; tr[1].r = 2;
    merge(root);
    return;
}

void zig(int &x)
//在进行左旋时，根节点会变换，所以加上& 
{
    int lx = tr[x].l;
    //记录当前tr[x].l的值 
    tr[x].l = tr[lx].r; tr[lx].r = x; x = lx;
    //注意画图，注意节点之间的位置 
    merge(tr[x].r); merge(x);
    //一定要先更新tr[x].r !!!!!
    return;
}

void zag(int &x)
{
    int rx = tr[x].r;
    tr[x].r = tr[rx].l; tr[rx].l = x; x = rx;
    merge(tr[x].l); merge(x);
    return;
}

void insert(int &x, int num) {
    if (!x) x = add(num);//如果没有节点num，则新建一个
    else if (tr[x].num == num) tr[x].cnt ++;
    else if (tr[x].num > num)
    {
        insert(tr[x].l, num);
        if (tr[tr[x].l].val > tr[x].val) zig(x);
    }
    else
    {
        insert(tr[x].r, num);
        if (tr[tr[x].r].val > tr[x].val) zag(x);
    }
    merge(x);
    return;
}

void erase(int &x, int num)
{
    if (!x) return;
    else if (tr[x].num == num)
    {
        if (tr[x].cnt > 1) tr[x].cnt --;
        else if (tr[x].l || tr[x].r)
        {
            if (!tr[x].r || tr[tr[x].l].val > tr[tr[x].r].val)
            {
                zig(x);
                erase(tr[x].r, num);
            }
            else
            {
                zag(x);
                erase(tr[x].l, num);
            }
        }
        else x = 0;
    }
    else if (tr[x].num > num) erase(tr[x].l, num);
    else erase(tr[x].r, num);
    merge(x);
    return;
}

int get_rank(int &x, int num)
{
    if (!x) return 0;//无解情况
    else if (tr[x].num == num) return tr[tr[x].l].size + 1;
    else if (tr[x].num > num) return get_rank(tr[x].l, num);
    else return tr[tr[x].l].size + tr[x].cnt + get_rank(tr[x].r, num);
}

int get_key(int u, int num)
{
    if(u == 0) return INF;
    if(tr[tr[u].l].size >= num) return get_key(tr[u].l, rank);//找左边
    if(tr[tr[u].l].size + tr[u].cnt >= rank) return tr[u].k;//如果满足条件就直接return
    return get_key(tr[u].r, rank - tr[tr[u].l].size - tr[u].cnt);//不然就找右边
}
int get_pr(int u, int k)//前驱
{
    if(u == 0) return -INF;
    if(tr[u].k >= k) return get_pr(tr[u].l, k);//找左边
    return max(get_pr(tr[u].r, k), tr[u].k);//可能是右边可能是这个数，所以用个max
}
int get_ne(int u, int k)//后继
{
    if(u == 0) return INF;//后继的写法和前驱相反，大家可以注意一下
    if(tr[u].k <= k) return get_ne(tr[u].r, k);
    return min(get_ne(tr[u].l, k), tr[u].k);
}

int main()
{
    build();//初始化

    cin >> T;//询问个数 
    while (T --)
    {
        int op, x;
        cin >> op >> x;

        if (op == 1) insert(root, x);//插入操作
        if (op == 2) erase(root, x);//删除操作
        if (op == 3) cout << get_rank(root, x) - 1<< endl;//查询排名 
        if (op == 4) insert(root, x);//《插入操作》
        if (op == 5) insert(root, x);//《插入操作》
        if (op == 6) insert(root, x);//《插入操作》
        cout << "root: " << root << endl;
        for(int i = 1;i <= now;++ i) {
            cout << tr[i].num << " " << tr[i].cnt << endl;
            cout << tr[i].num << " -> " << tr[i].l << " -> " << tr[i].r << endl;
            cout << endl;
        }
    }

    return 0;
}