数据结构--文艺平衡树（Splay）

模板传送门
很久以前我就听说Splay很好写，也很实用，今天晚上抄了一个看起来不错的代码，发现的确挺好懂，也挺好写，不过就是有点儿长了，刚好150行。
我还没有怎么好好研究过，这几天打算研究研究，所以我也不讲原理了，自行百度吧。
代码：

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cstdlib>
#include<cmath>
#include<vector>
#include<queue>
#define ll long long
using namespace std;
struct node{
    int ch[2];
    int fa;
    int cnt;
    int val;
    int son;
}t[500001];
int tot,root;
void pushup(int rt){
    t[rt].son=t[t[rt].ch[0]].son+t[t[rt].ch[1]].son+t[rt].cnt;
}
void rotate(int x){
    int y=t[x].fa;
    int z=t[y].fa;
    int k=t[y].ch[1]==x;
    t[z].ch[t[z].ch[1]==y]=x;
    t[x].fa=z;
    t[y].ch[k]=t[x].ch[k^1];
    t[t[x].ch[k^1]].fa=y;
    t[x].ch[k^1]=y;
    t[y].fa=x;
    pushup(y);
    pushup(x);
}
void splay(int x,int goal){
    while(t[x].fa!=goal){
        int y=t[x].fa;
        int z=t[y].fa;
        if(z!=goal){
            (t[y].ch[1]==x)^(t[z].ch[1]==y)?rotate(x):rotate(y);
        }
        rotate(x);
    }
    if(goal==0){
        root=x;
    }
}
void insert(int x){
    int u=root;
    int fa=0;
    while(u&&x!=t[u].val){
        fa=u;
        u=t[u].ch[x>t[u].val];
    }
    if(u){
        t[u].cnt++;
    }
    else{
        u=++tot;
        if(fa){
            t[fa].ch[x>t[fa].val]=u;
        }
        t[u].ch[0]=t[u].ch[1]=0;
        t[u].val=x;
        t[u].cnt=t[u].son=1;
        t[u].fa=fa;
    }
    splay(u,0);
}
void Find(int x){
    int u=root;
    if(!u){
        return;
    }
    while(t[u].ch[x>t[u].val]&&x!=t[u].val){
        u=t[u].ch[x>t[u].val];
    }
    splay(u,0);
}
int Next(int x,int f){
    Find(x);
    int u=root;
    if((t[u].val<x&&!f)||(t[u].val>x&&f))return u;
    u=t[u].ch[f];
    while(t[u].ch[f^1])u=t[u].ch[f^1];
    return u;
}
void Delete(int x){
    int a=Next(x,0);
    int b=Next(x,1);
    splay(a,0);
    splay(b,a);
    int del=t[b].ch[0];
    if(t[del].cnt>1){
        t[del].cnt--;
        splay(del,0);
    }
    else{
        t[b].ch[0]=0;
    }
}
int Kth(int x){
    int u=root;
    if(x>t[u].son){
        return 0;
    }
    while(1){
        int y=t[u].ch[0];
        if(x>t[y].son+t[u].cnt){
            x-=t[y].son+t[u].cnt;
            u=t[u].ch[1];
        }
        else if(x<=t[y].son){
            u=y;
        }
        else{
            return t[u].val;
        }
    }
}
int main(){
    insert(-2000000000);
    insert(2000000000);
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        int opt,x;
        scanf("%d %d",&opt,&x);
        if(opt==1){
            insert(x);
        }
        else if(opt==2){
            Delete(x);
        }
        else if(opt==3){
            Find(x);
            printf("%d
",t[t[root].ch[0]].son);
        }
        else if(opt==4){
            printf("%d
",Kth(x+1));
        }
        else if(opt==5){
            printf("%d
",t[Next(x,0)].val);
        }
        else if(opt==6){
            printf("%d
",t[Next(x,1)].val);
        }
    }
    return 0;
}