Splay 完整代码

纯代码

#include <bits/stdc++.h>
const int N = 1e6 + 10;
int ch[N][3], fa[N], size[N], cnt[N], key[N];
int Size, Root;
#define gc getchar()
inline int read() {
    int x = 0, f = 1; char c = gc;
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = gc;}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = gc;
    return x * f;
}
void Clear(int x) {
    ch[x][1] = ch[x][0] = cnt[x] = size[x] = fa[x] = key[x] = 0;
}
void Update(int x) {
    if (x) {
        size[x]=cnt[x];
        if (ch[x][0]) size[x]+=size[ch[x][0]];
        if (ch[x][1]) size[x]+=size[ch[x][1]];
    }
}
bool Get(int x) {
    return ch[fa[x]][1] == x;
}
void Rotate(int x) {
    int fax = fa[x], grfa = fa[fax], w = Get(x);
    ch[fax][w] = ch[x][w ^ 1];
    fa[ch[x][w ^ 1]] = fax;
    ch[x][w ^ 1] = fax;
    fa[fax] = x;
    fa[x] = grfa;
    ch[grfa][ch[grfa][1] == fax] = x;
    Update(fax);
    Update(x);
}
void Splay(int x) {
    for(int fax; fax = fa[x]; Rotate(x))
        if(fa[fax]) Rotate((Get(x) == Get(fax)) ? fax : x);
    Root = x;
}
void Insert(int x) {
    if(! Root) {
        Size ++;
        Root = Size;
        ch[Root][1] = ch[Root][0] = fa[Root] = 0;
        size[Root] = cnt[Size] = 1;
        key[Root] = x;
        return ;
    }
    int now = Root, fanow = 0;
    while(1) {
        if(x == key[now]) {
            cnt[now] ++;
            Update(now), Update(fanow);
            Splay(now);
            return ;
        }
        fanow = now;
        now = ch[now][key[now] < x];
        if(!now) {
            Size ++;
            ch[Size][0] = ch[Size][1] = 0;
            fa[Size] = fanow;
            ch[fanow][x > key[fanow]] = Size;
            size[Size] = cnt[Size] = 1;
            key[Size] = x;
            Update(fanow);
            Splay(Size);
            break;
        }
    }
}
int Pre() {
    int now = ch[Root][0];
    while(ch[now][1]) now = ch[now][1];
    return now;
}
int Nxt() {
    int now = ch[Root][1];
    while(ch[now][0]) now = ch[now][0];
    return now;
}
inline int Find(int x) {
    int now = Root, Ans = 0;
    while(1) {
        if(x < key[now]) now = ch[now][0];
        else {
            Ans += (ch[now][0] ? size[ch[now][0]] : 0);
            if(x == key[now]) {
                Splay(now);
                return Ans + 1;
            }
            Ans += cnt[now];
            now = ch[now][1];
        }
    }
}
inline int Findx(int x) {
    int now = Root;
    while(1) {
        if(ch[now][0] && x <= size[ch[now][0]]) now = ch[now][0];
        else {
            int imp = (ch[now][0] ? size[ch[now][0]] : 0) + cnt[now];
            if(x <= imp) return key[now];
            x -= imp;
            now = ch[now][1];
        }
    }
}
void Delete(int x) {
    int my = Find(x);
    if(cnt[Root] > 1) cnt[Root] --, Update(Root);
    else if(!ch[Root][1] && !ch[Root][0]) Clear(Root), Root = 0;
    else if(!ch[Root][0]) {
        int befroot = Root;
        Root = ch[Root][1];
        fa[Root] = 0;
        Clear(befroot);
    }
    else if(!ch[Root][1]) {
        int befroot = Root;
        Root = ch[Root][0];
        fa[Root] = 0;
        Clear(befroot);
    }
    else {
        int left = Pre(), befroot = Root;
        Splay(left);
        ch[Root][1] = ch[befroot][1];
        fa[ch[befroot][1]] = Root;
        Clear(befroot);
        Update(Root);   
    }
    return ;
}
int main() {
    int T = read();
    for(; T; T --) {
        int opt = read(), x = read();
        if(opt == 1) Insert(x);
        else if(opt == 2) Delete(x);
        else if(opt == 3) std:: cout << Find(x) << "\n";
        else if(opt == 4) std:: cout << Findx(x) << "\n";
        else if(opt == 5) {
            Insert(x);
            std:: cout << key[Pre()] << "\n";
            Delete(x);
        } else {
            Insert(x);
            std:: cout << key[Nxt()] << "\n";
            Delete(x);
        }
    }
    return 0;
}