Implicit key splay

#include <bits/stdc++.h>

struct node;
extern node *const null;

struct node {
    node *ch[2], *par;
    int value;
    int size;
    node(int val) : par(null), value(val), size(1) {
        ch[0] = ch[1] = null;
    }
    node() : par(this), value(0), size(0) {
        ch[0] = ch[1] = this;
    }
    void setCh(int x, node *n) {
        ch[x] = n;
        if (n != null)
            n->par = this;
    }
    node *delCh(int x) {
        node *res = ch[x];
        ch[x]->par = null;
        ch[x] = null;
        return res;
    }
};

node *const null = new node;

void update(node *nd) {
    nd->size = nd->ch[1]->size + 1 + nd->ch[0]->size;
}

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

void rot(node *nd) {
    node *pr = nd->par;
    int x = child(nd);
    if (pr->par != null)
        pr->par->setCh(child(pr), nd);
    nd->par = pr->par;
    pr->setCh(x, nd->ch[1 - x]);
    nd->setCh(1 - x, pr);
    update(pr);
    update(nd);
}

void splay(node *nd) {
    while (nd->par != null) {
        if (nd->par->par == null) {
            rot(nd);
        } else if (child(nd) == child(nd->par)) {
            rot(nd->par);
            rot(nd);
        } else {
            rot(nd);
            rot(nd);
        }
    }
}

node *access(node *root, int key) {
    node *cur;
    for (cur = root; cur->ch[0]->size != key;) {
        if (key < cur->ch[0]->size) {
            cur = cur->ch[0];
        } else {
            key -= cur->ch[0]->size + 1;
            cur = cur->ch[1];
        }
    }
    splay(cur);
    return cur;
}

void split(node *nd, int key, node *&left, node *&right) {
    if (key == nd->size) {
        left = nd;
        right = null;
        return;
    }
    right = access(nd, key);
    left = right->delCh(0);
    update(right);
}

node *merge(node *le, node *ri) {
    if (ri == null)
        return le;
    ri = access(ri, 0);
    ri->setCh(0, le);
    update(ri);
    return ri;
}

node *build(int l, int r) {
    if (l == r)
        return null;
    int m = (l + r) / 2;
    node *res = new node(m);
    res->setCh(0, build(l, m));
    res->setCh(1, build(m + 1, r));
    update(res);
    return res;
}

bool splay_check(node *nd, node *parent) {
    return (nd == null && nd->par == null && nd->ch[0] == null && nd->ch[1] == null && nd->size == 0 && nd->value == 0)
        || (nd->par == parent && splay_check(nd->ch[0], nd) && splay_check(nd->ch[1], nd)
         && nd->size == nd->ch[0]->size + 1 + nd->ch[1]->size);
}