Неявный splay

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

struct node {
    int l = 0, r = 0, p = 0, k = 0, s = 0;
} t[1001000];
int ptr = 1;
int new_node(int k) {
    int v = ptr++;
    t[v].s = 1;
    t[v].k = k;
    return v;
}
void pull(int v) {
    t[v].s = t[t[v].l].s + 1 + t[t[v].r].s;
}
int &son(int v, int i) {
    return i ? t[v].r : t[v].l;
}
void rot(int v) {
    int p = t[v].p, g = t[p].p;
    assert(v != p && v != g);
    int sv = t[p].r == v, sp = t[g].r == p;
    int &u = son(v, sv ^ 1);
    son(p, sv) = u, t[u].p = p, pull(p);
    u = p, t[p].p = v, pull(v);
    if (g) {
        son(g, sp) = v, t[v].p = g, pull(g);
    } else {
        t[v].p = 0;
    }
}
void splay(int v) {
    while (t[v].p) {
        int p = t[v].p, g = t[p].p;
        if (!g) {
            rot(v);
        } else if ((v == t[p].r) == (p == t[g].r)) {
            rot(p), rot(v);
        } else {
            rot(v), rot(v);
        }
    }
}
int by_order(int v, int k) {
    while (1) {
        int l = t[v].l;
        if (k < t[l].s) {
            v = t[v].l;
        } else if (k > t[l].s) {
            k -= t[l].s + 1;
            v = t[v].r;
        } else {
            splay(v);
            return v;
        }
    }
}
void print(int v) {
    if (v) {
        print(t[v].l);
        cout << t[v].k << " ";
        print(t[v].r);
    }
}
signed main() {
#ifdef LC
    assert(freopen("input.txt", "r", stdin));
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n, x, v = 0, u;
    cin >> n;
    n = 0;
    for (string s; cin >> s; ) {
        if (s == "add") {
            cin >> x;
            u = new_node(x);
            if (n) {
                v = by_order(v, n - 1);
                t[v].r = u, t[u].p = v, pull(v);
            } else {
                v = u;
            }
            ++n;
        } else if (s == "take") {
            if (n >= 2) {
                v = by_order(v, n - 2);
                t[v].r = 0, pull(v);
                --n;
            } else {
                v = 0, n = 0;
            }
        } else if (n >= 2) {
            v = by_order(v, n / 2 - 1), u = t[v].r;
            t[v].r = 0, t[u].p = 0, pull(v);
            v = by_order(v, 0), u = by_order(u, t[u].s - 1);
            t[v].l = u, t[u].p = v, pull(v);
        }
    }
    cout << n << endl;
    print(v);
    return 0;
}