思路

用5个数组表示左右子树，大小，权值，次数。节点编号从1开始，编号0代表空节点。由于二叉搜索树不能有重复的节点，用num数组记录某个节点权值重复的次数。也就是节点编号和权值是一一对应的，重复的权值用num记录。

#include <cstdio>
using namespace std;
const int N=1e5+10,INF=2147483647;
int n,root,cnt,opt,x;
int l[N],r[N],sz[N],val[N],num[N];
inline void update(int root){
    sz[root]=sz[l[root]]+sz[r[root]]+num[root];
}
inline int add(int x){
    l[++cnt]=0,r[cnt]=0,sz[cnt]=1,val[cnt]=x,num[cnt]=1;
    return cnt;
}
void insert(int x,int root){
    if(x<val[root]){
        if(l[root]==0) l[root]=add(x);//root的左节点为空，则增加一个权值为x的节点挂到root的左子树。
        else insert(x,l[root]);//不为空就继续递归，直到找到空或和权值等同的地方。
    }
    else if(x>val[root]){
        if(r[root]==0) r[root]=add(x);//右子树空就添加一个权值为x的节点挂上。
        else insert(x,r[root]);//不空就继续递归
    }
    else num[root]++;//若找到x==val[root]的就增加次数数组num的对应值
    update(root);//找到位置后，会使root及以上层次的节点都变化，故都要更新一下。
}
int rank(int x,int root){//查找数x的排名
    if(root==0) return 1;//root是0是返回1，这里指到了叶子节点后退出机制。
    if(x<val[root]) return rank(x,l[root]);//右子树所有数都比x大，故进入左子树
    if(x>val[root]) return rank(x,r[root])+sz[l[root]]+num[root];//左子树所有数都比x小，故进入右子树并加上左子树的size
    return sz[l[root]]+num[root];
}
/*不能写成这样，因为sz[root]包含左右子树的大小
int kth(int x,int root){
    if(x<sz[root]) return kth(x,l[root]);
    if(x>sz[root]) return kth(x-sz[l[root]]-num[root],r[root]);
    return val[root];
}
*/
int kth(int x,int root){//查排名，节点属性只有节点的大小和次数，利用这2个属性计算排名
    if(x<=sz[l[root]]) return kth(x,l[root]);//若排名x小于等于左子树的大小，则递归左子树
    if(x==sz[l[root]]+num[root]) return val[root];//若排名x等于左子树+root的次数，则排名x的数是root
    return kth(x-sz[l[root]]-num[root],r[root]);//否则递归右子树，排名x减去左子树及root的次数后的排名值
}
int main(){
    scanf("%d",&n);
    root=add(INF);//root设到最大值是挡住比集合内的值都大时的x
    while(n--){
        scanf("%d%d",&opt,&x);
        if(opt==1) printf("%d\n",rank(x,root));//root是1号但排名是计算大小和次数得出的
        else if(opt==2) printf("%d\n",kth(x,root));
        else if(opt==3) printf("%d\n",kth(rank(x,root)-1,root));
        else if(opt==4) printf("%d\n",kth(rank(x+1,root),root));
        else insert(x,root);
    }
    return 0;
}