Splay 模板

自己写的模板。

#include <cstdio>
const int N = 200000;
struct node {int d, n, c, f, son[2];}tr[N];
int cnt, root;
void up(int x) {
    int lc = tr[x].son[0], rc = tr[x].son[1];
    tr[x].c = tr[lc].c + tr[rc].c + tr[x].n;
}
int type(int son) {return tr[tr[son].f].son[1] == son;}
void set(int son, int fat, int w) {
    tr[tr[fat].son[w] = son].f = fat;
}
void new_node(int d, int f) {
    cnt++; tr[cnt].d = d;
    tr[cnt].c = tr[cnt].n = 1;
    tr[cnt].son[0] = tr[cnt].son[1] = 0;
    set(cnt, f, tr[cnt].d > tr[f].d);
}
void rot(int x, int w) {
    int f = tr[x].f, ff = tr[f].f;
    set(tr[x].son[w^1], f, w);
    set(x, ff, type(f));
    set(f, x, w^1);
    up(f); up(x);
}
void splay(int x, int rt = 0) {
    while(tr[x].f != rt) {
        int f = tr[x].f, ff = tr[f].f;
        if(ff == rt) rot(x, type(x));
        else if(type(x) == type(f))
            rot(f, type(f)), rot(x, type(x));
        else rot(x, type(x)), rot(x, type(x));
    }
    if(rt == 0) root = x;
}
int find(int d) {
    int x = root;
    while(tr[x].d != d) {
        int lc = tr[x].son[0], rc = tr[x].son[1];
        if(d < tr[x].d) {
            if(lc == 0) break;
            x = lc;
        } else {
            if(rc == 0) break;
            x = rc;
        }
    }
    return x;
}
void insert(int d) {
    if(root == 0) {
        new_node(d, 0);
        root = cnt;
        return;
    }
    int x = find(d);
    if(tr[x].d == d) {
        tr[x].n++; up(x);
        splay(x);
    } else {
        new_node(d, x);
        up(x); splay(cnt);
    }
}
void erase(int d) {
    int x = find(d); splay(x);
    if(tr[x].n > 1) {
        tr[x].n--;
        up(x);
        return;
    }
    int lc = tr[x].son[0], rc = tr[x].son[1];
    if(lc + rc == 0) {root = cnt = 0; return;}
    while(lc && tr[lc].son[1]) lc = tr[lc].son[1];
    if(lc) splay(lc, x); set(rc, lc, 1);
    root = lc ? lc : rc; tr[root].f = 0;
    up(root);
}
int rank(int d) {
    int x = find(d); splay(x);
    return tr[tr[x].son[0]].c + 1;
}
int kth(int k) {
    int x = root;
    while(true) {
        int lc = tr[x].son[0], rc = tr[x].son[1];
        if(k <= tr[lc].c) x = lc;
        else if(k > tr[lc].c + tr[x].n) {
            k -= tr[lc].c + tr[x].n;
            x = rc;
        } else break;
    }
    splay(x);
    return tr[x].d;
}
int pre(int d) {
    int x = find(d); splay(x);
    if(d <= tr[x].d && tr[x].son[0]) {
        x = tr[x].son[0];
        while(tr[x].son[1]) x = tr[x].son[1];
    }
    return tr[x].d;
}
int suc(int d) {
    int x = find(d); splay(x);
    if(d >= tr[x].d && tr[x].son[1]) {
        x = tr[x].son[1];
        while(tr[x].son[0]) x = tr[x].son[0];
    }
    return tr[x].d;
}
int main() {
    int n; scanf("%d", &n);
    for(int i=1; i<=n; i++)
    {
        int opt, x;
        scanf("%d%d", &opt, &x);
        switch(opt) {
            case 1: insert(x); break;
            case 2: erase(x); break;
            case 3: printf("%d\n", rank(x)); break;
            case 4: printf("%d\n", kth(x)); break;
            case 5: printf("%d\n", pre(x)); break;
            case 6: printf("%d\n", suc(x)); break;
        }
    }
    return 0;
}