Scapegoat Tree

#include <cstdio>

#include <algorithm>
#include <iostream>

#define ERRF(FMT...) // fprintf(stderr, FMT)

struct ScapegoatTree {
    struct Node {
        int key, w;
        Node *ls, *rs;
    };

    static const int N = 100010;
    static const double ALPHA = 0.6;

    Node* root;
    Node** scapegoatNode;

    static Node* create(int key) {
        static Node pool[N];
        static Node* p = pool;
        p->key = key;
        p->w = 2;
        return p++;
    }

    static int get_w(Node* p) {
        return p ? p->w : 1;
    }

    static void printLine(Node* p, Node** line) {
        if (!p)
            return;
        printLine(p->ls, line);
        line[get_w(p->ls) - 1] = p;
        printLine(p->rs, line + get_w(p->ls));
    }

    static Node* build(Node** begin, Node** end) {
        if (begin == end)
            return NULL;
        Node** mid = begin + (end - begin) / 2;
        Node* p = *mid;
        p->ls = build(begin, mid);
        p->rs = build(mid + 1, end);
        p->w = get_w(p->ls) + get_w(p->rs);
        return p;
    }

    static void scapegoat(Node** p) {
        ERRF("SCAPEGOAT %d NODES\n", (*p)->w - 1);
        static Node* line[N];
        printLine(*p, line);
        Node* tmp = build(line, line + (*p)->w - 1);
        *p = tmp;
    }

    void recursionInsert(Node*& p, int key) {
        if (!p) {
            p = create(key);
            return;
        }
        ++p->w;
        if (key < p->key)
            recursionInsert(p->ls, key);
        else
            recursionInsert(p->rs, key);
        if (std::max(get_w(p->ls), get_w(p->rs)) >= ALPHA * p->w)
            scapegoatNode = &p;
    }

    void recursionErase(Node*& p, int key) {
        if (p->key == key) {
            Node** q = &p->ls;
            if (!*q) {
                p = p->rs;
                return;
            }
            if (!(*q)->rs) {
                (*q)->rs = p->rs;
                p = *q;
                p->w = get_w(p->ls) + get_w(p->rs);
                return;
            }
            while ((*q)->rs) {
                --(*q)->w;
                q = &(*q)->rs;
            }
            Node* tmp = *q;
            *q = tmp->ls;
            tmp->ls = p->ls;
            tmp->rs = p->rs;
            p = tmp;
            p->w = get_w(p->ls) + get_w(p->rs);
            return;
        }
        --p->w;
        if (key < p->key)
            recursionErase(p->ls, key);
        else
            recursionErase(p->rs, key);
        if (std::max(get_w(p->ls), get_w(p->rs)) >= ALPHA * p->w)
            scapegoatNode = &p;
    }

    void insert(int key) {
        scapegoatNode = NULL;
        recursionInsert(root, key);
        if (scapegoatNode)
            scapegoat(scapegoatNode);
    }

    void erase(int key) {
        scapegoatNode = NULL;
        recursionErase(root, key);
        if (scapegoatNode)
            scapegoat(scapegoatNode);
    }

    int at(int k) const {
        Node* p = root;
        while (p) {
            if (k == get_w(p->ls))
                return p->key;
            if (k < get_w(p->ls))
                p = p->ls;
            else {
                k -= get_w(p->ls);
                p = p->rs;
            }
        }
        return 0;
    }

    int rank(int key) const {
        int ret = 1;
        Node* p = root;
        while (p) {
            if (p->key < key) {
                ret += get_w(p->ls);
                p = p->rs;
            } else
                p = p->ls;
        }
        return ret;
    }

    int prev(int key) const {
        int ret = 0;
        Node* p = root;
        while (p) {
            if (p->key < key) {
                ret = p->key;
                p = p->rs;
            } else
                p = p->ls;
        }
        return ret;
    }

    int post(int key) const {
        int ret = 0;
        Node* p = root;
        while (p) {
            if (p->key > key) {
                ret = p->key;
                p = p->ls;
            } else
                p = p->rs;
        }
        return ret;
    }
} scapegoatTree;

const int N = 100010;

int main() {
//  freopen("test.in", "r", stdin);
    int n;
    scanf("%d", &n);
    while (n--) {
        int opt, x;
        scanf("%d%d", &opt, &x);
        ERRF("%d %d\n", opt, x);
        switch (opt) {
            case 1:
                scapegoatTree.insert(x);
                break;
            case 2:
                scapegoatTree.erase(x);
                break;
            case 3:
                printf("%d\n", scapegoatTree.rank(x));
                break;
            case 4:
                printf("%d\n", scapegoatTree.at(x));
                break;
            case 5:
                printf("%d\n", scapegoatTree.prev(x));
                break;
            case 6:
                printf("%d\n", scapegoatTree.post(x));
                break;
            default:break;
        }
    }
    return 0;
}