<----求个赞QwQ

这里给出一个像$set$一样可以用的平衡树——$Treap$
使用方法：

treap <int> t;
t.insert (x);
t.erase (x);
t.get_rank (x).key;
t.get_key (rank).key
t.get_next (x).key
t.get_prev (x).key

代码如下：

#include <iostream>
#include <ctime>
using namespace std;
const int N = 1000010,INF = 1e9;
namespace std {
    template <typename T>
    struct treap_Node {
        int l,r;
        T key;
        int val;
        int cnt,size;
    };
    int root,idx;
    template <typename type>
    struct treap {
        treap_Node <type> tr[N];
        type neg_INF,pos_INF;
        treap (type neg_INF,type pos_INF) {
            this->neg_INF = neg_INF,this->pos_INF = pos_INF;
            srand (time (0));
        }
        int get_node (type key) {
            tr[++idx].key = key,tr[idx].val = rand (),tr[idx].cnt = tr[idx].size = 1;
            return idx;
        }
        treap_Node <type> neg_INF_node = tr[get_node (neg_INF)],pos_INF_node = tr[get_node (pos_INF)];
        void push_up (int p) {
            tr[p].size = tr[tr[p].l].size + tr[tr[p].r].size + tr[p].cnt;
        }
        void left_rotate (int &p) {
            int q = tr[p].r;
            tr[p].r = tr[q].l,tr[q].l = p,p = q;
            push_up (tr[p].l),push_up (p);
        }
        void right_rotate (int &p) {
            int q = tr[p].l;
            tr[p].l = tr[q].r,tr[q].r = p,p = q;
            push_up (tr[p].r),push_up (p);
        }
        void insert (type key,int &p = root) {
            if (!p) p = get_node (key);
            else if (tr[p].key == key) tr[p].cnt++;
            else if (key < tr[p].key) {
                insert (key,tr[p].l);
                if (tr[tr[p].l].val > tr[p].val) right_rotate (p);
            }
            else {
                insert (key,tr[p].r);
                if (tr[tr[p].r].val > tr[p].val) left_rotate (p);
            }
            push_up (p);
        }
        void erase (type key,bool all = false,int &p = root) {
            if (!all) {
                if (!p) return ;
                if (tr[p].key == key) {
                    if (tr[p].cnt > 1) tr[p].cnt--;
                    else if (tr[p].l || tr[p].r) {
                        if (!tr[p].r || tr[tr[p].l].val > tr[tr[p].r].val) {
                            right_rotate (p);
                            erase (key,tr[p].r);
                        }
                        else {
                            left_rotate (p);
                            erase (key,tr[p].l);
                        }
                    }
                    else p = 0;
                }
                else if (tr[p].key > key) erase (key,tr[p].l);
                else erase (key,tr[p].r);
                push_up (p);
            }
            else {
                if (!p) return ;
                if (tr[p].key == key) {
                    if (tr[p].l || tr[p].r) {
                        if (!tr[p].r || tr[tr[p].l].val > tr[tr[p].r].val) {
                            right_rotate (p);
                            erase (key,tr[p].r);
                        }
                        else {
                            left_rotate (p);
                            erase (key,tr[p].l);
                        }
                    }
                    else p = 0;
                }
                else if (tr[p].key > key) erase (key,tr[p].l);
                else erase (key,tr[p].r);
                push_up (p);
            }
        }
        int get_rank (type key,int p = root) {
            if (!p) return 0;
            if (tr[p].key == key) return tr[tr[p].l].size + 1;
            if (tr[p].key > key) return get_rank (key,tr[p].l);
            return tr[tr[p].l].size + tr[p].cnt + get_rank (key,tr[p].r);
        }
        treap_Node <type> get_key (int rank,int p = root) {
            if (!p) return pos_INF_node;
            if (tr[tr[p].l].size >= rank) return get_key (rank,tr[p].l);
            if (tr[tr[p].l].size + tr[p].cnt >= rank) return tr[p];
            return get_key (rank - tr[tr[p].l].size - tr[p].cnt,tr[p].r);
        }
        treap_Node <type> get_prev (type key,int p = root) {
            if (!p) return neg_INF_node;
            if (tr[p].key >= key) return get_prev (key,tr[p].l);
            treap_Node <type> x = get_prev (key,tr[p].r);
            return tr[p].key > x.key ? tr[p] : x;
        }
        treap_Node <type> get_next (type key,int p = root) {
            if (!p) return pos_INF_node;
            if (tr[p].key <= key) return get_next (key,tr[p].r);
            treap_Node <type> x = get_next (key,tr[p].r);
            return tr[p].key < x.key ? tr[p] : x;
        }
    };
}