splay tree

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

#define null NULL

struct splay_tree {
private:
    struct node {
        int key;
        node *l, *r, *p;
        node() {
            l = r = p = null;
            key = 0;
        }
        node(int key) {
            this->key = key;
            l = r = p = null;
        }
    };
    typedef node *tnode;
    node *root;
    void set_parent(tnode child, tnode parent) {
        if (child) {
            child->p = parent;
        }
    }
    void keep_parent(tnode v) {
        set_parent(v->l, v);
        set_parent(v->r, v);
    }
    void rotate(tnode child, tnode parent) {
        assert(child);
        assert(parent);
        assert(parent->l == child || parent->r == child);
        assert(child->p == parent);
        tnode gparent = parent->p;
        if (gparent) {
            (gparent->l == parent ? gparent->l : gparent->r) = child;
        }
        if (parent->l == child) {
            parent->l = child->r;
            child->r = parent;
        } else {
            parent->r = child->l;
            child->l = parent;
        }
        keep_parent(child);
        keep_parent(parent);
        child->p = gparent;
    }
    tnode splay(tnode v) {
        if (!v->p)
            return v;
        if (!v->p->p) {
            rotate(v, v->p);
            return v;
        }
        tnode parent = v->p;
        tnode gparent = parent->p;
        bool zigzig = (parent->l == v) == (gparent->l == parent);
        if (zigzig) {
            rotate(parent, gparent);
            rotate(v, parent);
        } else {
            rotate(v, parent);
            rotate(v, gparent);
        }
        return splay(v);
    }
    tnode find(tnode v, int key) {
        if (!v)
            return null;
        if (key == v->key) {
            return splay(v);
        }
        if (v->key > key && v->l) {
            return find(v->l, key);
        } else if (v->key < key && v->r) {
            return find(v->r, key);
        }
        return splay(v);
    }
    void split_without_del(tnode t, int key, tnode &l, tnode &r) {
        if (!t) {
            l = r = null;
            return;
        }
        t = find(t, key);
        if (t->key < key) {
            r = t->r;
            set_parent(r, null);
            l = t;
            l->r = null;
        } else {
            l = t->l;
            set_parent(l, null);
            r = t;
            r->l = null;
        }
    }
    void split(tnode t, int key, tnode &l, tnode &r) {
        if (!t) {
            l = r = null;
            return;
        }
        t = find(t, key);
        if (t->key == key) {
            l = t->l;
            r = t->r;
            set_parent(l, null);
            set_parent(r, null);
        } else if (t->key < key) {
            r = t->r;
            set_parent(r, null);
            l = t;
            l->r = null;
        } else {
            l = t->l;
            set_parent(l, null);
            r = t;
            r->l = null;
        }
    }
    tnode merge(tnode l, tnode r) {
        if (!l)
            return r;
        if (!r)
            return l;
        r = find(r, l->key);
        r->l = l;
        l->p = r;
        return r;
    }
    void remove(tnode &root, int key) {
        tnode t = find(root, key);
        tnode l = t->l;
        tnode r = t->r;
        set_parent(l, null);
        set_parent(r, null);
        root = merge(l, r);
    }
    void insert(tnode &root, int key) {
        tnode l, r;
        split(root, key, l, r);
        tnode v = new node(key);
        root = merge(merge(l, v), r);
    }
public:
    splay_tree() {
        root = null;
    }
    void insert(int val) {
        insert(root, val);
    }
    int find(int val) {
        tnode l, r;
        split_without_del(root, val, l, r);
        int ans = -1;
        if (r) {
            r = find(r, INT_MIN);
            ans = r->key;
        }
        root = merge(l, r);
        return ans;
    }
};

int main(int argc, char **argv) {

}