TREAP

#include <iostream>
#include <cstdlib>
#include <functional>
using namespace std;


/* TREAP
based on ubcarchive treap code by luccasiau@gmail.com
*/

template<class T, class P, class C>
class Treap {
public:
    Treap *l, *r;
    T v;
    P p;
    C lz, count;
    Treap(T v_ = T(), P p_ = P()) : l(NULL), r(NULL), v(v_), p(p_), lz(C()), count(1) {}
    void lazy() {
        if (this == NULL) return;
        /*insert your lazy-propagation here (only use it in implicit)*/
    }
    C getCount() const { return (this == NULL) ? 0 : count; }
    void update() {
        if (this == NULL) return;
        count = l->getCount() + r->getCount() + 1;
        lazy();
        /*update your update*/
    }
    static Treap* merge(Treap *a, Treap *b) { // regular & implicit
        Treap* ret = NULL;
        a->lazy(); b->lazy();
        if (a == NULL) return b;
        else if (b == NULL) return a;
        else if (a->p < b->p) {
            ret = b;  b->l = Treap::merge(a, b->l);
        }
        else {
            ret = a;  a->r = Treap::merge(a->r, b);
        }
        ret->update();
        return ret;
    }
    Treap* operator[](int k) { // 0-indexed. Kth element from left to right
        lazy();
        int lc = l->getCount();
        if (k - lc == 0) return this;
        else if (k < lc) return l->operator[](k);
        else return r->operator[](k - lc - 1);
    }
    Treap* split(Treap *&a, Treap *&b, T key, function<bool(T, T)> toleft = less_equal<T>()) {
        lazy();
        if (!this) a = b = NULL;
        else if (toleft(v, key)) { a = this; r->split(r, b, key, toleft); }
        else { b = this; l->split(a, l, key, toleft); }
        update();
        return a;
    }
    Treap* insert(Treap *x) {
        lazy();
        Treap *l = NULL, *r = NULL;
        split(l, r, x->v);
        return Treap::merge(Treap::merge(l, x), r);
    }
    Treap* remove(T v) {
        lazy();
        Treap *a = NULL, *b = NULL, *aa = NULL, *ab = NULL;
        split(a, b, v);
        a->split(aa, ab, v, less<T>());
        return Treap::merge(aa, b);
    }
    Treap* find(T x, function<bool(T, T)> lessop = less<T>()) {
        if (!lessop(v,x) && !lessop(x,v)) return this;
        else if (lessop(v,x)) return r ? r->find(x, lessop) : NULL;
        else return l ? l->find(x, lessop) : NULL;
    }
};
template<class T, class P, class C>
ostream& operator<<(ostream& os, const Treap<T,P,C>& x){
    if (&x == NULL) return os<<"()";
    return os << "(" << *(x.l) << x.v << *(x.r) << ")";
}


//example usage:
int main() {
    Treap<int,int,int>* x=NULL;
    for (int i = 10; i >=0; i--) {
        int v = rand();
        x = x->insert(new Treap<int, int, int>(v,rand()));
        cout << (*x) << endl << endl;
        if (i % 3 == 0) {
            x = x->remove(v);
            cout << "after removal" << (*x) << endl << endl;
        }
    }
    return 0;
}