ALGO Implicit Treap

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

namespace Mlxa {
    #define read cin
    #define eol endl
    #define print(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 all(x) begin(x), end(x)
    #define size(x) ll(x.size())
} using namespace Mlxa;
typedef long long  ll;

mt19937 getRand;

struct node {
    ll val, s, p;
    node *l, *r;
    node (ll V, ll P) : val(V), s(0), p(P), l(nullptr), r(nullptr) {}
    node (ll V) : node(V, getRand()) {}
}; typedef node* ptr; ptr tree;

ll getSize (ptr v)  { if (v) return v->s; return 0; }

void update (ptr v) { assert(v); v->s = getSize(v->l) + getSize(v->r) + 1; }

void out (ptr v)    { println(v->p, v->val, "\t\t ", v->s); }

void dfsPrint (ll t, ptr v) {
    if (v) {
        dfsPrint(t + 1, v->r);
        for (ll i(t); i --;) print(' '); out(v);
        dfsPrint(t + 1, v->l); }
}

void split (ptr root, ptr &l, ptr &r, ll num) {
    if (root) {
        ll num_of_root = getSize(root->l);
        if (num_of_root < num)
             split(root->r, root->r, r, num - (num_of_root + 1)), l = root;
        else split(root->l, l, root->l, num), r = root;
        update(root);
    } else l = r = nullptr;
}

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

void insert (ptr &root, ll num, ptr ins) {
    if (root) { assert(ins && !ins->l && !ins->r);
        ll num_of_root = getSize(root->l);
        assert(0 <= num && num <= root->s);
        if (root->p > ins->p) {
            if (num_of_root < num)
                 insert(root->r, num - (num_of_root + 1), ins);
            else insert(root->l, num, ins);
        }
        else split(root, ins->l, ins->r, num), root = ins;
    }
    else root = ins;
    update(root);
}
inline void insert (ptr& root, ll pos, ll val) { insert(root, pos, new node(val)); }
inline void erase(ptr &root, ll num)
{   assert(root); assert(0 <= num); assert(num < getSize(root));
    ptr left(nullptr), middle(nullptr), right(nullptr);
    split(root, left, middle, num);
    split(middle, middle, right, num + 1);
    delete middle; middle = merge(middle->l, middle->r);
    root = merge( merge(left, middle), right );
}

int main () {
    tree = new node(777, numeric_limits<ll>::max()); const ll rep(2*1000*1000);
    for (ll i(0); i < rep; ++ i) insert(tree, i, 5*i+19);
    for (ll ost(rep - 1); ost --;) erase(tree, 0);
    return 0;
}