Splay

#include <cstdlib>
#include <limits>
#include <cstdint>
#include <utility>
typedef struct node {
    node *ch[2], *par;
    int key;
    node(int key) : ch{0, 0}, par(0), key(key) {}
    void setCh(bool x, node *n) {
        if (n)
            n->par = this;
        ch[x] = n;
    }
    node *delCh(bool x) {
        node *res = ch[x];
        if (res)
            res->par = 0;
        ch[x] = 0;
        return res;
    }
} *Node;

bool child(node *n) {
    return n->par->ch[1] == n;
}

void rot(node *new_root) {
    node *root = new_root->par;
    if (root->par)
        root->par->setCh(child(root), new_root);
    bool x = child(new_root);
    root->setCh(x, new_root->ch[!x]);
    new_root->setCh(!x, root);
}

node *splay(node *n) {
    while (n && n->par) {
        if (!n->par->par) {
            rot(n);
        } else if (child(n) == child(n->par)) {
            rot(n->par);
            rot(n);
        } else {
            rot(n);
            rot(n);
        }
    }
    return n;
}

node *access(node *n, int key) {
    if (n->key == key) {
        return splay(n);
    }
    bool x = n->key < key;
    if (n->ch[x])
        return access(n->ch[x], key);
    else
        return splay(n);
}

node *merge(node *l, node *r) {
    if (!l)
        return r;
    l = access(l, std::numeric_limits<int>::max());
    l->setCh(1, r);
    return l;
}

std::pair<node *, node *> spit(node *t, int key) {
    if (!t)
        return std::pair<node *, node *>(nullptr, nullptr);
    t = access(t, key);
    if (t->key < key)
        return std::pair<node *, node *>(t, t->delCh(1));
    else
        return std::pair<node *, node *>(t->delCh(0), t);
}