题目 写的替罪羊树，35pts。
代码:

#include <iostream>
using namespace std;
const int N = 1e6 + 10;
const double alp = 0.75;
struct Node {
	int Ls, rs;
	int val;
	int Tot;
	int size;
	int del;
} tr[N];
int order[N], cnt;
int tr_stack[N], top;
int root = 0;
// 拍扁 
void inor (int u) {
	if (!u)
		return;
	inor(tr[u].Ls);
	if (tr[u].del)
		order[++ cnt] = u;
	else
		tr_stack[++ top] = u;
	inor(tr[u].rs);
}
void InitNode (int u) {
	tr[u].Ls = tr[u].rs = 0;
	tr[u].size = tr[u].Tot = tr[u].del = 1;
}
void update (int u) {
	tr[u].size = tr[tr[u].Ls].size + tr[tr[u].rs].size + 1;
	tr[u].Tot = tr[tr[u].Ls].Tot + tr[tr[u].rs].Tot + 1;
}
// 重建树
void build (int L, int r, int &u) {
	int mid = L + r >> 1;
	u = order[mid];
	if (L == r) {
		InitNode(u);
		return;
	}
	if (L < mid)
		build(1, mid - 1, tr[u].Ls);
	if (L == mid)
		tr[u].Ls = 0;
	build(mid + 1, r, tr[u].rs);
	update(u);
}
void rebuild (int &u) {
	cnt = 0;
	inor(u);
	if (cnt)
		build(1, cnt, u);
	else
		u = 0;
}
bool check (int u) {
	return 1.0 * tr[u].size * alp <= max(1.0 * tr[tr[u].Ls].size, 1.0 * tr[tr[u].rs].size);
//	if (1.0 * tr[u].size * alp <= max(1.0 * tr[tr[u].Ls].size, 1.0 * tr[tr[u].rs].size))
//		return true;
//	else return false;
}
void ins (int &u, int x) {
	if (!u) {
		u = tr_stack[top --];
		tr[u].val = x;
		InitNode(u);
		return;
	}
	tr[u].size ++;
	tr[u].Tot ++;
	if (tr[u].val >= x)
		ins(tr[u].Ls, x);
	else
		ins(tr[u].rs, x);
	if (check(u))
		rebuild(u);
}
int Rank (int u, int x) {
	if (u == 0)
		return 0;
	if (x > tr[u].val)
		return tr[tr[u].Ls].size + tr[u].del + Rank(tr[u].rs, x);
	return Rank(tr[u].Ls, x);
}
int kth (int k) {
	int u = root;
	while (u) {
		if (tr[u].del && tr[tr[u].Ls].size + 1 == k)
			return tr[u].val;
		else if (tr[tr[u].Ls].size >= k)
			u = tr[u].Ls;
		else {
			k -= tr[tr[u].Ls].size + tr[u].del;
			u = tr[u].rs;
		}
	}
	return tr[u].val;
}
void del_rank (int &u, int k) {
	tr[u].size --;
	if (tr[u].del && tr[tr[u].Ls].size + 1 == k) {
		tr[u].del = 0;
		return;
	}
	if (tr[tr[u].Ls].size + tr[u].del >= k)
		del_rank(tr[u].Ls, k);
	else
		del_rank(tr[u].rs, k - tr[tr[u].Ls].size - tr[u].del);
}
void del (int x) {
	del_rank(root, Rank(root, x) + 1);
	if (1.0 * tr[root].Tot * alp >= tr[root].size)
		rebuild(root);
}
signed main () {
	ios::sync_with_stdio(false);
	cin.tie(nullptr), cout.tie(nullptr);
	for (int i = N - 1; i >= 1; i --)
		tr_stack[++ top] = i;
	int q;
	cin >> q;
	while (q --) {
		int op, x;
		cin >> op >> x;
		if (op == 1)
			ins(root, x);
		else if (op == 2)
			del(x);
		else if (op == 3)
			cout << Rank(root, x) + 1 << '\n';
		else if (op == 4)
			cout << kth(x) << '\n';
		else if (op == 5)
			cout << kth(Rank(root, x)) << '\n';
		else if (op == 6)
			cout << kth(Rank(root, x + 1) + 1) << '\n';
	}
	return 0;
}