TreapImplictKey

template<typename T>
struct item {
    int prior, c = 0;
    T key;
    item* l, * r;
    item(T key, int prior) : key(key), prior(prior), l(NULL), r(NULL) { }
};

template<typename T>
struct dyn_array {
    item<T>* treap = 0;
    void upd(item<T>* x) {
        x->c = (x->l ? x->l->c : 0) + 1 + (x->r ? x->r->c : 0);
    }

    void split(item<T>* t, int pos, item<T>*& l, item<T>*& r) {
        if (!t)
            l = r = NULL;
        else if (pos <= (t->l ? t->l->c : 0))
            split(t->l, pos, l, t->l), r = t, upd(t);
        else
            split(t->r, pos - (t->l ? t->l->c : 0) - 1, t->r, r), l = t, upd(t);
    }

    void merge(item<T>*& t, item<T>* l, item<T>* r) {
        if (!l || !r)
            t = l ? l : r;
        else if (l->prior > r->prior)
            merge(l->r, l->r, r), t = l, upd(t);
        else
            merge(r->l, l, r->l), t = r, upd(t);
    }

    void print(item<T>*& t) {
        if (!t) return;
        print(t->l);
        cout << t->key << " ";
        print(t->r);
    }

    void print() {
        print(treap);
    }

    void insert(item<T>*& t, int pos, T tit) {
        item<T>* l, * r, * x;
        item<T>* it = new item<T>(tit, rand() * rand());
        it->c = 1;
        split(t, pos - 1, l, r);
        merge(x, l, it);
        merge(t, x, r);
    }

    void insert(int pos, T tit) {
        insert(treap, pos, tit);
    }

    void erase1(item<T>*& t, int key) {
        int l = (t->l ? t->l->c : 0);
        if (key - 1 == l)
            merge(t, t->l, t->r);
        else
            erase1(key - 1 < l ? t->l : t->r, key - 1 < l ? key : key - l - 1), upd(t);
    }

    void erase(int pos) {
        erase1(treap, pos);
    }

    void update(int pos, T v) {
        erase(pos);
        insert(pos, v);
    }

    T operator[](int x) {
        item<T>* l, * r;
        split(treap, x, l, r);
        if (!treap) return -1;
        item<T>* cp = l;
        if (!cp) return -1;
        while (cp->r) cp = cp->r;
        T res = cp->key;
        merge(treap, l, r);
        return res;
    }

    size_t size() {
        return treap ? treap->c : 0;
    }
};