求助替罪羊树

今天晚上想学习一下替罪羊树，顺利的过掉了普通版的数据，跑得也比之前写的其他平衡树快一些，但是在加强版却只有50分，我将alpha分别改为0.8，0.85，0.9分别得到了60分，80分和90分但是按道理系数这么大是不太对劲的。另外我突发奇想在求排名，kth等操作之中都判断一下平衡，但是直接就成了MLE，求哪位巨佬帮忙检查一下板子，代码里面写上了注释，感激不尽。

#include <cstdio>
#include <cstring>
#include <algorithm>
const int N = 5e6 + 10;
const double alpha = 0.75;
#define rint register int
int read() {
    int s = 0, f = 1;
    char ch = getchar();
    while(ch < '0' || ch > '9') {
        if(ch == '-') f = -1;
        ch = getchar();
    }
    while(ch >= '0' && ch <= '9') {
        s = (s << 1) + (s << 3) + (ch ^ 48);
        ch = getchar();
    }
    return s * f;
}
struct Tree {
    int ch[2], val, siz, liv; //ch为两个儿子，val为权值,siz为节点个数（未知是否存在），liv为存在的节点个数
    bool exist;
} tree[N];
#define ls(t) tree[t].ch[0] //分别表示左右儿子和中点
#define rs(t) tree[t].ch[1]
#define mid ((l + r) >> 1)
int root;
int Pool[N], tail, tot, cnt[N], top; //Pool是内存池用tail做指针，cnt数组暂存被重构的节点用top做指针
int New(rint val) { //新建一个节点
    rint pos = tail ? Pool[tail--] : ++tot;
    tree[pos].ch[0] = tree[pos].ch[1] = 0;
    tree[pos].val = val;
    tree[pos].siz = tree[pos].liv = tree[pos].exist = 1;
    return pos;
}
bool isbad(rint t) { //判断是否需要重构
    rint now = std::max(tree[ls(t)].siz, tree[rs(t)].siz);
    if((double)tree[t].siz * alpha <= now) return true;
    return false;
}
void dfs(int t) { //中序遍历，取出重构的序列
    if(ls(t)) dfs(ls(t));
    if(tree[t].exist) cnt[++top] = t;
    else Pool[++tail] = t;
    if(rs(t)) dfs(rs(t));
}
void pushup(int t) { //向上修改
    tree[t].siz = tree[ls(t)].siz + tree[rs(t)].siz + 1;
    tree[t].liv = tree[ls(t)].liv + tree[rs(t)].liv + tree[t].exist;
}
void build(rint &t, rint l, rint r) { //重构树
    if(l > r) return t = 0, void();
    t = cnt[mid];
    build(ls(t), l, mid - 1);
    build(rs(t), mid + 1, r);
    pushup(t);
}
void rebuild(rint &t) { //重构一条龙
    top = 0;
    dfs(t);
    build(t, 1, top);
}
void Insert(rint &t, rint val) { //插入节点
    if(!t) { //到达叶子
        t = New(val);
        return;
    }
    tree[t].siz++; tree[t].liv++; 
    if(isbad(t)) rebuild(t); //判断重构
    if(val <= tree[t].val) Insert(ls(t), val);
    else Insert(rs(t), val);
    pushup(t);
}
void del_kth(rint t, rint rnk) { //删除第k个节点
    rint x = tree[ls(t)].liv;
    if(tree[t].exist && x + 1 == rnk) {
        tree[t].exist = 0; 
        tree[t].liv--;
        return;
    }
    tree[t].liv--;
    if(x >= rnk) del_kth(ls(t), rnk);
    else del_kth(rs(t), rnk - x - tree[t].exist);
}
int kth(rint t, rint k) { //求出第k个节点
    rint x = tree[ls(t)].liv;
    if(tree[t].exist && x + 1 == k) {
        return tree[t].val;
    }
    if(x >= k) return kth(ls(t), k);
    else return kth(rs(t), k - x - tree[t].exist);
}
int rank(rint t, rint val) { //求排名
    if(!t) return 0;
    int x = tree[ls(t)].liv + tree[t].exist;
    if(tree[t].val < val) return rank(rs(t), val) + x;
    else return rank(ls(t), val);
}
void del(rint val) { //删除节点
    rint rnk = rank(root, val) + 1;
    del_kth(root, rnk);
}
int pre(rint val) { //求前趋
    rint rnk = rank(root, val);
    return kth(root, rnk);
}
int nxt(rint val) { //求后继
    rint rnk = rank(root, val + 1) + 1;
    return kth(root, rnk);
}
int main() {
    rint n = read(), m = read(), res = 0, ans = 0;
    for(rint i = 1; i <= n; ++i) {
        rint w = read();
        Insert(root, w);
    }
    for(rint i = 1; i <= m; ++i) {
        rint op = read(), x = read();
        x ^= res;
        if(op == 1) Insert(root, x);
        else if(op == 2) del(x);
        else if(op == 3) res = rank(root, x) + 1;
        else if(op == 4) res = kth(root, x);
        else if(op == 5) res = pre(x);
        else if(op == 6) res = nxt(x);
        if(op != 1 && op != 2) ans ^= res;
    }
    printf("%d\n", ans);
    return 0;
}