splay除了样例全部TLE。求教！！！

#include<iostream>
#define NUM 1000010
using namespace std;
int fa[NUM]={0},ch[NUM][2]={0},sz[NUM]={0},cnt[NUM]={0},root=0,tot=0,a[NUM]={0};
int n;
int which(int x){
    if(fa[x]==0) return -1;
    return x==ch[fa[x]][0]?0:1;
}
void mt(int x){
    sz[x]=sz[ch[x][0]]+sz[ch[x][1]]+cnt[x];
}
void rotate(int x){
    int f,ff,wch,wchf;
    f=fa[x];ff=fa[f];wch=which(x);wchf=which(f);
    if(wchf!=-1) ch[ff][wchf]=x;
    ch[f][wch]=ch[x][wch^1]; 
    ch[x][wch^1]=f;
    fa[f]=x;
    fa[x]=ff;
    if(ch[f][wch]) fa[ch[f][wch]]=f;
    mt(x),mt(f);
}
void splay(int x){
    for(int f=fa[x];f=fa[x],f;rotate(x)){
        if(fa[f]) rotate((which(x)==which(f)?f:x));
    }
    root=x;
}
void insert(int v){
    if(!root){
        a[++tot]=v;
        root=tot;
        cnt[tot]++;
        mt(root);
        return ;
    }
    int cur=root,f=0;
    while(true){
        if(!cur){
            a[++tot]=v;
            cnt[tot]++;
            fa[tot]=f;
            ch[f][(v>a[f])]=tot;
            mt(f),mt(tot);
            splay(tot);
            return;
        }
        if(v==a[cur]){
            cnt[cur]++;
            mt(cur),mt(f);
            splay(cur);
            return;
        }
        f=cur;
        cur=(v<a[cur]?ch[cur][0]:ch[cur][1]);
    }
}
int rk(int x){
    int cur=root,res=0;
    while(true){
        if(cur==0) return 0;
        if(a[cur]>x)
        cur=ch[cur][0];
        else{
            res+=sz[ch[cur][0]];
            if(a[cur]==x){
                splay(cur);
                return res+1;
            }
            res+=cnt[cur];
            cur=ch[cur][1];
        }
    }
}
int xth(int x){
    int cur=root;
    while(true){
        if(ch[cur][0]&&x<=sz[ch[cur][0]])
        cur=ch[cur][0];
        else{
            x-=sz[ch[cur][0]]+cnt[cur];
            if(x<=0){
                splay(cur);
                return a[cur];
            }
            cur=ch[cur][1]; 
        }
    }
}
int pre(){
    int cur=ch[root][0];
    if(!cur) return 0;
    while(ch[cur][1]) cur=ch[cur][1];
    // splay(cur);
    return cur;
}
int nxt(){
    int cur=ch[root][1];
    if(!cur) return 0;
    while(ch[cur][0]) cur=ch[cur][0];
    // splay(cur);
    return cur;
}
void clear(int x){
    ch[x][0]=ch[x][1]=fa[x]=sz[x]=cnt[x]=0;
}
void del(int x){
    rk(x);
    if(cnt[root]>1){
        cnt[root]--;
        mt(root);
        return;
    }
    if(!ch[root][0]&&!ch[root][1]){
        clear(root);
        root=0;
        return;
    }
    if(!ch[root][0]){
        int t=root;
        root=ch[root][1];
        fa[root]=0;
        clear(t);
        return;
    }
    if(!ch[root][1]){
        int t=root;
        root=ch[root][0];
        fa[root]=0;
        clear(t);
        return;
    }
    int cur=root;
    int t=pre();
    fa[ch[root][1]]=t;
    fa[t]=0;
    ch[t][1]=ch[cur][1];
    clear(cur);
    root=t;
    mt(root);
}
void _traverse(int x);
void traverse(int x){
    cout<<"--------"<<endl;
    _traverse(x);
    cout<<endl<<"--------"<<endl;
}
void _traverse(int x){
    if(!x) return;
    _traverse(ch[x][0]);
    cout<<a[x]<<" ";
    _traverse(ch[x][1]);
}
int main(){
    cin>>n;
    for(int i=0;i<n;i++){
        int choose,para;
        scanf("%d %d",&choose,&para);
        switch(choose){
            int t;
            case 1:insert(para);printf("%d\n",rk(para));del(para);break;
            case 2:printf("%d\n",xth(para));break;
            case 3:insert(para);t=pre();printf("%d\n",(t==0?-2147483647:a[t]));del(para);break;
            case 4:insert(para);t=nxt();printf("%d\n",(t==0?2147483647:a[t]));del(para);break;
            case 5:insert(para);break;
        }
    }
    return 0;
}