今天晚上想学习一下替罪羊树，顺利的过掉了普通版的数据，跑得也比之前写的其他平衡树快一些，但是在加强版却只有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;
}