RT,48分,我菜死了

#include<bits/stdc++.h>
using namespace std;
const int INF=1e9;
int ch[100002][2];
int size[100002],val[100002];
int dat[100002],cnt[100002];
int root;
int num=0;
inline int Rand()
{
    static long long r=2333;
    return (r*=65463)%=2147483647;
}
int init(int v)
{
    val[++num]=v;
    dat[num]=Rand();
    size[num]=1;
    cnt[num]=1;
    return num;
}
void pushup(int i)
{
    size[i]=size[ch[i][0]]+size[ch[i][1]]+cnt[i];
}
void build()
{
    root=init(-INF);
    ch[root][1]=init(INF);
    pushup(root);
}
void rotate(int &i,int d)   //d=0——左旋  d=1——右旋
{
    int t=ch[i][d^1];
    ch[i][d^1]=ch[t][d];
    ch[t][d]=i;
    i=t;
    pushup(ch[i][d]);
    pushup(i);
}
void add(int &i,int v)
{
    if(!i){
        i=init(v);
        return ;
    }
    if(val[i]==v)
        cnt[i]++;
    else
    {
        if(v<val[i])
            add(ch[i][0],v);
        else
            add(ch[i][1],v);
    }
    pushup(i);
}
void remove(int &i,int v)
{
    if(!i)
        return ;
    if(v==val[i]){
        if(cnt[i]>1)
            cnt[i]--;
        if(ch[i][0]||ch[i][1]){
            if(!ch[i][1]||dat[ch[i][0]]>dat[ch[i][1]]){
                rotate(i,1);
                remove(ch[i][1],v);
            }
            else{
                rotate(i,0);
                remove(ch[i][0],v);
            }
            pushup(i);
        }
        else
            i=0;
        return ;
    }
    v<val[i] ? remove(ch[i][0],v):remove(ch[i][1],v);
    pushup(i);
}
int get_pre(int v)
{
    int i=root;
    int p;
    while(i){
        if(val[i]<v){
            p=val[i];
            i=ch[i][1];
        }
        else
            i=ch[i][0];
    }
    return p;
}
int get_next(int v)
{
    int i=root;
    int p;
    while(i){
        if(val[i]>v){
            p=val[i];
            i=ch[i][0];
        }
        else
            i=ch[i][1];
    }
    return p;
}
int get_rank(int i,int v)
{
    if(!i)
        return 0;
    if(val[i]==v)
        return size[ch[i][0]]+1;
    else if(val[i]>v)
        return get_rank(ch[i][0],v);
    else
        return size[ch[i][0]]+cnt[i]+get_rank(ch[i][1],v);
}
int get_val(int i,int rk)
{
    if(!i)
        return INF;
    if(rk<=size[ch[i][0]])
        return get_val(ch[i][0],rk);
    else if(rk<=size[ch[i][0]]+cnt[i])
        return val[i];
    else
        return get_val(ch[i][1],rk-size[ch[i][0]]-cnt[i]);
}
int main()
{
    build();
    int n;
    cin>>n;
    int i;
    for(i=1;i<=n;i++){
        int op,x;
        cin>>op>>x;
        if(op==1)
            add(root,x);
        else if(op==2)
            remove(root,x);
        else if(op==3)
            cout<<get_rank(root,x)-1<<endl;
        else if(op==4)
            cout<<get_val(root,x+1)<<endl;
        else if(op==5)
            cout<<get_pre(x)<<endl;
        else if(op==6)
            cout<<get_next(x)<<endl;
    }
    return 0;
}