splay tree 2

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

#define null NULL

struct splay_tree {
private:
    struct node {
        int key, sz, m;
        node *l, *r, *p;
        node() {
            l = r = p = null;
            key = sz = m = 0;
        }
        node(int key) {
            this->key = m = key;
            sz = 1;
            l = r = p = null;
        }
    };
    typedef node *tnode;
    node *root;
    inline void set_parent(tnode child, tnode parent) {
        if (child) {
            child->p = parent;
        }
    }
    inline void keep_parent(tnode v) {
        set_parent(v->l, v);
        set_parent(v->r, v);
    }
    inline int get_sz(tnode v) {
        return (v ? v->sz : 0);
    }
    inline int get_min(tnode v) {
        return (v ? v->m : INT_MAX);
    }
    inline void upd(tnode v) {
        if (v) {
            v->sz = 1 + get_sz(v->l) + get_sz(v->r);
            v->m = min(v->key, min(get_min(v->l), get_min(v->r)));
        }
    }
    void rotate(tnode child, tnode 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);
        upd(parent);
        upd(child);
        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;
        if ((parent->l == v) == (gparent->l == parent)) {
            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 (get_sz(v->l) < key) {
            key -= get_sz(v->l);
        } else {
            return find(v->l, key);
        }
        if (key == 1) {
            return splay(v);
        }
        return find(v->r, key - 1);
    }
    void split(tnode t, int key, tnode &l, tnode &r) {
        if (!t) {
            l = r = null;
            return;
        }
        if(key == 0){
            l = null;
            r = t;
            return;
        }
        if(key == get_sz(t)){
            l = t;
            r = null;
            return;
        }
        t = find(t, key + 1);
        l = t->l;
        r = t;
        r->l = null;
        set_parent(l, null);
        upd(l);
        upd(r);
    }
    tnode merge(tnode l, tnode r) {
        if (!l)
            return r;
        if (!r)
            return l;
        r = find(r, 1);
        assert(get_sz(r->l) == 0);
        r->l = l;
        l->p = r;
        upd(r);
        return r;
    }
    inline int _get_min(int l, int r) {
        tnode t1, t2, t3;
        split(root, r, t2, t3);
        split(t2, l - 1, t1, t2);
        int ans = t2->m;
        root = merge(t1, t2);
        root = merge(root, t3);
        return ans;
    }
    inline void _add(int pos, int val) {
        tnode t1, t2 = new node(val), t3;
        split(root, pos, t1, t3);
        root = merge(t1, t2);
        root = merge(root, t3);
    }
    void print(tnode t){
        if(!t)
            return;
        print(t->l);
        cout << t->key << " ";
        print(t->r);
    }
public:
    splay_tree() {
        root = null;
    }
    int get_min(int l, int r){
        return _get_min(l, r);
    }
    void add(int pos, int val){
        _add(pos, val);
    }
    void print(){
        print(root);
        cout << endl;
    }
};

#define endl "\n"

int main(int argc, char **argv) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    return 0;
}