关于Treap随机数的疑问

#include<bits/stdc++.h>
#define lson a[p].l
#define rson a[p].r
#define inf 0x7fffffff
const int N=1e5+10;
struct Treap{
    int l,r;
    int dat,val;
    int cnt,siz;
}a[N];
int tot,root;
//std::mt19937 rd(std::time(nullptr));
int New(int val){
    a[++tot].val=val;
    a[tot].cnt=a[tot].siz=1;
    a[tot].dat=std::rand();
    return tot;
}
void update(int p){
    a[p].siz=a[p].cnt+a[a[p].l].siz+a[a[p].r].siz;
}
void build(){
    New(-inf),New(inf);
    root=1;a[1].r=2;
    update(root);
}
int rank_by_val(int p,int val){
    if(p==0)return 1;
    if(a[p].val==val)return a[a[p].l].siz+1;
    if(val<a[p].val)return rank_by_val(a[p].l,val);
    else return rank_by_val(a[p].r,val)+a[a[p].l].siz+a[p].cnt;
}
int val_by_rank(int p,int rk){
    if(p==0)return inf;
    if(a[a[p].l].siz>=rk)return val_by_rank(a[p].l,rk);
    if(a[a[p].l].siz+a[p].cnt>=rk)return a[p].val;//
    else return val_by_rank(a[p].r,rk-a[a[p].l].siz-a[p].cnt);
}
void zig(int &p){//右旋，p为变成右子节点的父节点
    int q=a[p].l;
    a[p].l=a[q].r,a[q].r=p,p=q;
    update(a[p].r);update(p);
}
void zag(int &p){//左旋，p为变成左子节点的父节点
    int q=a[p].r;
    a[p].r=a[q].l,a[q].l=p,p=q;
    update(a[p].l);update(p);
}
void Insert(int &p,int val){
    if(p==0){
        p=New(val);
        return ;
    }
    if(val==a[p].val){
        a[p].cnt++;update(p);
        return ;
    }
    if(val<a[p].val){
        Insert(a[p].l,val);
        if(a[p].dat<a[lson].dat)zig(p);
    }else{
        Insert(a[p].r,val);
        if(a[p].dat<a[rson].dat)zag(p);
    }
    update(p);
}
void Remove(int &p,int val){
    if(p==0)return ;
    if(val==a[p].val){
        if(a[p].cnt>1){
            a[p].cnt--;update(p);
            return ;
        }
        if(a[p].l || a[p].r){
            if(a[p].r==0 || a[lson].dat>a[rson].dat){
                zig(p);Remove(a[p].r,val);
            }else{
                zag(p);Remove(a[p].l,val);
            }
            update(p);
        }else p=0;
        return ;
    }
    (val<a[p].val?Remove(a[p].l,val):Remove(a[p].r,val));
    update(p);
}

int getpre(int val){
    int p=root,ans=1;
    while(p){
        if(a[p].val<val)ans=p,p=a[p].r;
        else p=a[p].l;
    }
    return a[ans].val;
}
int getnext(int val){
    int p=root,ans=2;
    while(p){
        if(a[p].val>val)ans=p,p=a[p].l;
        else p=a[p].r;
    }
    return a[ans].val;
}
/*
int getpre(int val){
    int ans=1;
    int p=root;
    while(p){
        if(val==a[p].val){
            if(a[p].l>0){
                p=a[p].l;
                while(a[p].r>0)p=a[p].r;
                ans=p;
            }
            break;
        }
        if(a[p].val<val && a[p].val>a[ans].val)ans=p;
        p=(val<a[p].val?lson:rson);
    }
    return a[ans].val;
}
int getnext(int val){
    int ans=2;
    int p=root;
    while(p){
        if(val==a[p].val){
            if(a[p].r>0){
                p=a[p].r;
                while(a[p].l>0)p=a[p].l;
                ans=p;
            }
            break;
        }
        if(a[p].val>val && a[p].val<a[ans].val)ans=p;
        p=(val<a[p].val?lson:rson);
    }
    return a[ans].val;
}
*/
int main(){
    //freopen("P3369_1.out","w",stdout);
    std::ios::sync_with_stdio(false);
    std::cout.tie(nullptr);
    std::cin.tie(nullptr);

    build();
    int q;
    std::cin>>q;
    while(q--){
        int op,x;
        std::cin>>op>>x;
        if(op==1){
            Insert(root,x);
        }else if(op==2){
            Remove(root,x);
        }else if(op==3){
            std::cout<<rank_by_val(root,x)-1<<"\n";
        }else if(op==4){
            std::cout<<val_by_rank(root,x+1)<<"\n";
        }else if(op==5){
            std::cout<<getpre(x)<<"\n";
        }else if(op==6){
            std::cout<<getnext(x)<<"\n";
        }
        //for(int i=1;i<=tot;i++){
        //    std::cout<<a[i].val<<" "<<a[i].l<<" "<<a[i].r<<" "<<a[i].siz<<" \n";
        //}
        //std::cout<<"\n";
    }
    return 0;
}