宗法树求助

#include<cstdio>
#include<cstring>
using namespace std;
#define Max(_A,_B) (_A>_B?_A:_B)
#define Min(_A,_B) (_A<_B?_A:_B)
const int maxn = 400007;
struct Node{
    int val, siz;//siz表示子树内叶子（数）的个数
    Node *ls, *rs;
    Node() : val(0), siz(0), ls(NULL), rs(NULL){};
    Node(int v,int s,Node *l,Node *r){
        val = v, siz = s, ls = l, rs = r;
    }
    bool isLeaf(){
        return ls == NULL;
    }
    void pushup(){
        //为了防止pushup的错误调用 在这里判断是否是叶子结点
        if(!isLeaf()){
            siz = ls->siz + rs->siz;
            val = Max(ls->val, rs->val);
        }
    }
}pool[maxn];
Node *root = NULL;
Node *newNode(int val,int siz,Node *ls,Node *rs){
    static int cnt = 0;
    pool[cnt] = Node(val, siz, ls, rs);
    return &pool[cnt++];
}

void insert(Node *&cur,int x){
    if(cur==NULL)
        cur = newNode(x, 1, NULL, NULL);
    else{
        if(cur->isLeaf()){
            cur->ls = newNode(Min(x, cur->val), 1, NULL, NULL);
            cur->rs = newNode(Max(x, cur->val), 1, NULL, NULL);
        }else{
            if(x>cur->ls->val) //比左大 插到右边
                insert(cur->rs, x);
            else
                insert(cur->ls, x);
        }
        cur->pushup();
    }
}
void erase(Node *cur,Node *fa,int x){
    if(cur==NULL)
        return;
    if(cur->isLeaf()){
        if(fa!=cur){
            if(fa->ls==cur){
                *fa = *fa->rs;
            }
            else if(fa->rs==cur&&fa->ls!=NULL)
                *fa = *fa->ls;
            else{//fa是叶子结点 cur也是 -》只有一个点
                root = NULL;
                return;
            }
        }
    }
    else{
        if(x>cur->ls->val)//在右子树
            erase(cur->rs, cur, x);
        else
            erase(cur->ls, cur, x);
    }
    cur->pushup();
}
int rnk(Node *cur,int x){//往右走的时候加上左子树的siz
//如果查一个比树内所有元素都大的值
    if(cur->isLeaf()){
        if(x>cur->val)//可以直接在查询之前特判根结点
        {
            return 2;//最大排名+1
        }
        return 1;
    }else{
        if(x>cur->ls->val){
            return rnk(cur->rs, x) + cur->ls->siz;
        }
        else{
            return rnk(cur->ls, x);
        }
    }
}

int kth(Node *cur,int k){
    if(cur->isLeaf())
        return cur->val;
    else{
        if(k>cur->ls->siz){
            return kth(cur->rs, k - cur->ls->siz);
        }else{
            return kth(cur->ls, k);
        }
    }
}
int main(){
    int n,opt,x;
    
    scanf("%d", &n);
    for (int i = 1; i <= n;i++){
        scanf("%d%d", &opt, &x);
        if(opt==1)
            insert(root, x);
        if(opt==2)
            erase(root, root, x);
        if(opt==3){
            if(root->isLeaf()&&root->val==x)
                printf("1\n");
            else
                printf("%d\n", rnk(root, x));
        }
        if(opt==4)
            printf("%d\n", kth(root, x));
        if(opt==5)
            printf("%d\n", kth(root, rnk(root, x) - 1));
        if(opt==6)
            printf("%d\n", kth(root, rnk(root, x + 1)));
    }
        return 0;
}