OST-treap

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

namespace Mlxa {
    #define read cin
    #define eol endl
    template <class A> inline void
    print (A a) { cout << a << ' '; }
    template <class A> inline void
    println (A a) { cout << a << eol; }
    template <class A, class... B> inline void
    println (A a, B... b) { print(a), println(b...); }
    #define w(...) println(__VA_ARGS__)
    #define limit numeric_limits
    #define all(x) begin(x), end(x)
} using namespace Mlxa;
typedef long long  ll;


namespace Node
{
    mt19937 getRand;
    struct node
    {
        ll k, p, s;
        node *l, *r;
        node (ll K, ll P) : k(K), p(P), s(1) {l = r = nullptr;}
        node (ll K) : node(K, getRand()) {}
    }; typedef node *ptr;

    inline ll getSize (ptr v) { return v ? v->s : 0; }
    inline void update (ptr v) { if (v) v->s = 1 + getSize(v->l) + getSize(v->r); }

    void out (ptr v, ll t = 0, const char* tab = "", const char* sep = "")
    {   if (v) {
            out(v->l, t + 1, tab, sep);
            for (ll i(0); i < t; ++ i ) cout << tab; cout << v->k << " " << v->s << sep;
            out(v->r, t + 1, tab, sep);
        }
    }

    ll find_by_order (ptr v, ll n)
    {
        assert(v && "Out of range(((");
        ll numv = getSize(v->l);
        if (n == numv) return v->k;
        if (n < numv) return find_by_order(v->l, n);
        return find_by_order(v->r, n - (numv + 1));
    }

    void split (ptr v, ptr &l, ptr &r, ll key)
    {
        if (v) {
            if (key < v->k) {
                split(v->l, l, v->l, key);
                r = v;
                update(l);
                update(r);
            } else {
                split(v->r, v->r, r, key);
                l = v;
                update(l);
                update(r);
            }
        } else l = r = nullptr;
    }

    ptr merge (ptr l, ptr r)
    {
        if (l && r) {
            if(l->k > r->k) swap(l, r);
            if (l-> p > r->p) {
                l->r = merge(l->r, r);
                update(l);
                update(r);
                return l;
            } else {
                r->l = merge(r->l, l);
                update(l);
                update(r);
                return r;
            }
        } else return l ? l : r;
    }

    void erase (ptr &v, ll key)
    {
        ptr l, m, r; l = m = r = nullptr;
        split(v, l, m, key - 1); // Test
        split(m, m, r, key);
        // Maybe delete m
        v = merge(l, r);
    }

    void erase_one (ptr &v, ll key)
    {
        ptr l, m, r; l = m = r = nullptr;
        split(v, l, m, key - 1); // Test
        split(m, m, r, key);
        m = merge(m->l, m->r);
        // Maybe delete m
        v = merge(merge(l, m), r);
    }

    void insert (ptr &v, ll key)
    {
        ptr l, r, i; l = r = nullptr;
        i = new node(key);
        split(v, l, r, key);
        v = merge(merge(l, i), r);
    }
}

using namespace Node;
struct OST
{
    string name;
    ptr root;
    OST () : root(new node(-1e18, limit<ll>::max())) {}
    OST (string s) : OST () { name = s; }
    void clear () { root = new node(-1e18, limit<ll>::max()); }
    ll size () { update(root); return getSize(root) - 1; }
    ll operator [] (ll i) { return Node::find_by_order(root, i + 1);  }
    ll find_by_order (ll i) { return Node::find_by_order(root, i + 1); }
    void insert (ll k) { Node::insert(root, k); }
    void erase (ll k) { Node::erase(root, k); }
    void erase_one (ll k) { Node::erase_one(root, k); }
    void out () { w("out", name); Node::out(root, 0, "[]", "\n"); w("\nend", name); }
};


int main ()
{
    OST o("test...");
    o.insert(-1);
    o.insert(1);
    o.insert(1);
    o.insert(2);
    o.insert(2);
    o.insert(5);
    o.out();
    o.erase_one(1);
    o.out();
    return 0;
}