splay板子

#include <bits/stdc++.h>

using namespace std;
const int maxn = 100000+5;
struct Splay{
    int ch[maxn][0],ch[maxn][1],fa[maxn],siz[maxn],key[maxn],tot;
    void init(int t, int val = 0, int par = 0){
        ch[t][0] = ch[t][1] = 0; key[t] = val; fa[t] = par; key[t] = val;
    }
    void up(int t){
        siz[t] = siz[ch[t][1]] + siz[ch[t][0]];
    }
    void init(){
        init(0, 0, 0);
        tot = root = 0;
    }
    int find(int t = root, int x){
        if(!t)return 0;
        if(x == key[t]){
            splay(t, 0);
            return t;
        }
        if(x < key[t])return find(ch[t][0], x);
        else return find(ch[t][1], x);
    }
    void rotate(int x, int d){
        int y = fa[x];
        ch[y][d^1] = ch[x][d];
        if(ch[x][d])fa[ch[x][d]] = y;
        fa[x] = fa[y];
        if(fa[y]){
            if(y == ch[fa[y]][0])ch[fa[y]][0] = x;
            else ch[fa[y]][1]] = x;
        }    
        ch[x][d] = y;
        up(x), up(y);
    }
    void splay(int x, int targrt){
        
        while(x != targrt){
            int y = fa[x];
            if(x == ch[y][0]){
                if(targrt && y == ch[fa[y]][0])
                    rotate(y, 1);
                rotate(x, 1);
            }
            else {
                if(targrt && y == ch[fa[y]][1])
                    rotate(y, 0);
                rotate(x, 0);
            }
        }
        if(!targrt)root = x;
    }
    void insert(int t = root, int x, int par = 0){
        if(!t){
            t = ++tot;    
            init(t, x, par);
            splay(t, 0);
        }
        else {
            int cur = t;
            if(x < key[t])insert(ch[t][0], x, cur);
            else insert(ch[t][1], x, cur);
        }
    }
    
    int rank(int t = root,int x){
        if(!t)return 0;
        if(x == key[t])return 1;
        if(x < key[t])return query(ch[t][0], x);
        return 1+siz[ch[t][0]]+query(ch[t][1], x);
    }
    int query(int t = root, int x){
        if(!x)return t;
        if(x == siz[ch[t][0] + 1)return t;
        if(x > siz[ch[t][0]] + 1)
            return query(ch[t][1], x - 1 - siz[ch[t][0]]);
        return query(ch[t][0], x);
    }
    int Query(int x){
        printf("%d\n",val[query(x)]);
    }
    void erase(int x){
        int k = rank(x), lnd = query(k-1), rnd = query(k+1);
        splay(lnd, 0);splay(rnd, lnd);
        ch[rnd][0] = 0;
        up(rnd), up(lnd);
    }
   
    int getpre(int t = root, int x){
        if()
        
        
    }
    int getscc(int t = root, int x){
        if(!t)return x;
        if(t < key)return getscc(ch[t][1], x);
        if(t == key[t])return key[ch[t][1]];
        return key[ch[t][0] >= x ? getscc(ch[t][0], x) : key[t];
    }
}Tr;
int main()
{
    int n;
    scanf("%d",&n);
    while(n--){
        int opt,x;
        scanf("%d%d",&opt,&x);
        switch(opt){
            case 1:Tr.insert(x);break;
            case 2:Tr.erase(x);break;
            case 3:Tr.rank(x);break;
            case 4:Tr.Query(x);break;
            case 5:Tr.getpre(x);break;
            case 6:Tr.getscc(x);break;
        }
    }
    return 0;
}


/*
1. 插入x数
2. 删除x数(若有多个相同的数，因只删除一个)
3. 查询x数的排名(若有多个相同的数，因输出最小的排名)
4. 查询排名为x的数
5. 求x的前驱(前驱定义为小于x，且最大的数)
6. 求x的后继(后继定义为大于x，且最小的数)
*/