debug的时候发现此题解给出代码无法通过 test 6: in:

100
1 914241
1 639471
5 917713
6 912745
1 234811
1 297728
3 297728
1 6927
5 645391
1 664569
2 914241
1 134689
1 868271
1 842266
5 850426
1 286545
4 1
1 333833
1 274177
1 568845
1 157569
4 13
1 732493
4 7
4 9
5 646117
1 136381
1 473089
1 419305
1 639776
3 473089
4 7
6 234571
1 37685
1 321207
1 496713
1 531105
2 234811
2 157569
1 326601
1 317437
1 791873
1 931097
1 224521
3 317437
1 395823
1 877225
4 19
1 781729
4 17
6 529658
2 931097
1 578851
3 639776
1 112100
5 790233
1 338689
1 481883
1 735265
1 293813
5 143413
3 37685
4 25
4 21
1 679713
1 964201
1 733235
5 569757
1 608769
1 455372
6 314885
3 842266
5 782361
1 586193
1 666945
1 249761
5 739567
1 79651
3 136381
1 288892
4 26
1 176792
6 130671
1 437505
5 489981
3 842266
1 850205
1 509407
1 856047
1 50817
6 291536
1 314153
3 842266
1 237389
5 570526
6 322825
2 608769
6 315843
5 43637
1 184462

stdout:

914241
914241
2
639471
842266
6927
868271
297728
568845
639471
11
286545
234811
9
639471
531105
531105
21
781729
136381
2
639776
531105
568845
317437
35
781729
735265
6
568845
134689
481883
42
293813
45
568845
326601
317437
37685

read:

3 639776
1 112100
5 790233
1 338689

his code:

#include <bits/stdc++.h>
const double alpha = 0.7;
#define MAXN 2000001

inline int read() {
	int x = 0, f = 0; char c = getchar();
	for (; c < '0'; c = getchar()) if (c == '-') f = 1;
	for (; c > '.'; c = getchar()) x = (x << 3) + (x << 1) + (c ^ 48);
	return f ? -x : x;
}

namespace ScapegoatTree {
	struct node {
		int ch[2], val, size, tsize, real, fa;
	} e[MAXN];
	int cur[MAXN];
	int root, tot, cp, cnt, rb;
	
	int id(int u) {
		return e[e[u].fa].ch[1] == u;	
	}
	
	bool isbad(int u) {
		if (1.0 * e[u].tsize * alpha + 5 < 1.0 * e[e[u].ch[0]].tsize ||
			1.0 * e[u].tsize * alpha + 5 < 1.0 * e[e[u].ch[1]].tsize) 
			return true;
		else 
			return false;
	}

	void dfs(int u) {
		if (!u) return ;
		dfs(e[u].ch[0]);
		if (e[u].real) cur[++cp] = u;
		dfs(e[u].ch[1]);
	}

	void build(int l, int r, int &u, int fa = 0) {
		int mid = l + r >> 1;
		u = cur[mid];
		e[u].fa = fa;
		if (l == r) {
			e[u].ch[0] = e[u].ch[1] = 0;
			e[u].size = e[u].tsize = 1;
			return ;
		}
		if (l < mid) build(l, mid - 1, e[u].ch[0], u);
		else e[u].ch[0] = 0;
		build(mid + 1, r, e[u].ch[1], u);
		e[u].size = e[e[u].ch[0]].size + e[e[u].ch[1]].size + 1;
		e[u].tsize = e[e[u].ch[0]].tsize + e[e[u].ch[1]].tsize + e[u].real;
	}

	void rebuild(int &u) {
		cp = 0;
		dfs(u);
		if (cp) build(1, cp, u);
		else u = 0;
	}

	void insert(int &u, int val) {
		if (!u) {
			u = ++tot;
			e[u].val = val;
			e[u].real = e[u].size = e[u].tsize = 1;
			e[u].ch[0] = e[u].ch[1] = 0;
			return ;
		}
		e[u].size++, e[u].tsize++;
		if (e[u].val >= val) insert(e[u].ch[0], val);
		else insert(e[u].ch[1], val);
		if (isbad(u)) rb = u;
	}

	int kth(int k) {
		for (int u = root; u; ) {
			if (e[u].real && e[e[u].ch[0]].tsize + 1 == k)
				return e[u].val;
			if (e[e[u].ch[0]].tsize >= k)
				u = e[u].ch[0];
			else 
				k -= e[e[u].ch[0]].tsize + e[u].real,
				u = e[u].ch[1];
		}
	}

	int rank(int val) {
		int ans = 1;
		for (int u = root; u; ) {
			if (e[u].val >= val)
				u = e[u].ch[0];
			else 
				ans += e[e[u].ch[0]].tsize + e[u].real,
				u = e[u].ch[1];
		}
		return ans;
	}

	void pop_rk(int u, int rk) {
		if (e[u].real && e[e[u].ch[0]].tsize + 1 == rk) {
			e[u].real = 0;
			e[u].tsize--;
			return ;
		}
		e[u].tsize--;
		if (e[e[u].ch[0]].tsize + e[u].real >= rk)
			pop_rk(e[u].ch[0], rk);
		else 
			pop_rk(e[u].ch[1], rk - e[e[u].ch[0]].tsize - e[u].real);
	}

	void pop(int val) {
		pop_rk(root, rank(val));
		if (1.0 * e[root].size * alpha > e[root].tsize)
			rebuild(root);
	}
};
using namespace ScapegoatTree;

int main() {
//	freopen("tzys(better).out","w",stdout);
	int opt, x, Q;
	Q = read();
	while (Q--) {
		opt = read(); x = read();
		switch(opt) {
			case 1: 
				insert(root, x); 
				if (rb) {
					printf("?");
					rebuild(rb == root ? root : e[e[rb].fa].ch[id(rb)]);
					rb = 0;	
				}
				break;
			case 2: pop(x); break;
			case 3: printf("%d\n", rank(x)); break;
			case 4: printf("%d\n", kth(x)); break;
			case 5: printf("%d\n", kth(rank(x) - 1)); break;
			case 6: printf("%d\n", kth(rank(x + 1))); break;
		}
	}
	return 0;
}