Splay Tree

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

struct SplayTree {
    struct Node {
        Node *ch[2], *par;
        int val, sz, freq;
        Node() : sz(0), freq(0) { par = ch[0] = ch[1] = this; val = INT_MIN; }
        Node(int v) : val(v), sz(1), freq(1) { par = ch[0] = ch[1] = EMPTY; }
        void pull() { sz = freq + ch[0]->sz + ch[1]->sz; }
    };

    static Node* EMPTY;
    Node* root;

    SplayTree() : root(EMPTY) {}

    void link(Node* p, Node* c, int d) {
        if (p != EMPTY) { p->ch[d] = c; p->pull(); }
        if (c != EMPTY) c->par = p;
    }

    int dir(Node* p, Node* c) { return p->ch[1] == c; }

    void rotate(Node* p, int d) {
        Node* q = p->ch[d], *g = p->par;
        link(p, q->ch[!d], d);
        link(q, p, !d);
        link(g, q, dir(g, p));
    }

    void splay(Node* q) {
        while (q->par != EMPTY) {
            Node* p = q->par, *g = p->par;
            int d1 = dir(p, q), d2 = dir(g, p);
            if (g == EMPTY) rotate(p, d1);
            else if (d1 == d2) { rotate(g, d2); rotate(p, d1); }
            else { rotate(p, d1); rotate(g, d2); }
        }
        root = q;
    }

    Node* find(Node* p, int val) {
        if (p == EMPTY) return EMPTY;
        Node* c = p->ch[val > p->val];
        if (p->val == val || c == EMPTY) return p;
        return find(c, val);
    }

    void insert(int val) {
        if (root == EMPTY) { root = new Node(val); return; }
        root = find(root, val); splay(root);
        if (root->val == val) { root->freq++; root->sz++; return; }
        Node* q = new Node(val);
        int d = val > root->val;
        if (root->ch[d] != EMPTY) {
            Node* c = root->ch[d];
            link(root, EMPTY, d);
            link(q, c, q->val < c->val);
        }
        link(q, root, val > root->val ? 0 : 1);
        root = q;
    }

    void erase(int val) {
        root = find(root, val); splay(root);
        if (root->val != val) return;
        if (root->freq > 1) { root->freq--; root->sz--; return; }
        Node* l = root->ch[0], *r = root->ch[1];
        delete root;
        if (l != EMPTY) l->par = EMPTY;
        if (r != EMPTY) r->par = EMPTY;
        if (l == EMPTY) { root = r; return; }
        root = find(l, INT_MAX); splay(root);
        link(root, r, 1);
    }

    bool search(int val) {
        root = find(root, val); splay(root);
        return root->val == val;
    }

    int kth(int k) {
        Node* p = root;
        while (p != EMPTY) {
            int ls = p->ch[0]->sz;
            if (k < ls) p = p->ch[0];
            else if (k < ls + p->freq) { splay(p); return p->val; }
            else { k -= ls + p->freq; p = p->ch[1]; }
        }
        return -1;
    }

    int countLess(int val) {
        root = find(root, val); splay(root);
        return root->ch[0]->sz + (root->val < val ? root->freq : 0);
    }

    int size() { return root->sz; }
};

SplayTree::Node* SplayTree::EMPTY = new SplayTree::Node();