想尝试一下SBT结果...

#include <cstdio>
#include <cctype>

struct SBTNode {
	int val, rpt;
	int left, right, size;
};

struct SBT {
	SBTNode bst[100005];
	int pool, root;

	inline void lRorate(int &p) {
		int t = bst[p].right;
		bst[p].right = bst[t].left;
		bst[t].left = p;
		bst[t].size = bst[p].size;
		bst[p].size = bst[bst[p].left].size + bst[bst[p].right].size + bst[p].rpt;
		p = t;
	}

	inline void rRorate(int &p) {
		int t = bst[p].left;
		bst[p].left = bst[t].right;
		bst[t].right = p;
		bst[t].size = bst[p].size;
		bst[p].size = bst[bst[p].left].size + bst[bst[p].right].size + bst[p].rpt;
		p = t;
	}

	void maintain(int &p, int flag) {
		if (flag) {		// Considering the right
			if (bst[bst[p].right].size < bst[bst[bst[p].left].left].size) {
				rRorate(p);
			} else if (bst[bst[p].right].size < bst[bst[bst[p].left].right].size) {
				lRorate(bst[p].left);
				rRorate(p);
			} else return;
		} else {		// Considering the left
			if (bst[bst[p].left].size < bst[bst[bst[p].right].right].size) {
				lRorate(p);
			} else if (bst[bst[p].left].size < bst[bst[bst[p].right].left].size) {
				rRorate(bst[p].right);
				lRorate(p);
			} else return;
		}
		maintain(bst[p].left, 1);
		maintain(bst[p].right, 0);
		maintain(p, 1);
		maintain(p, 0);
	}

	void insert(int &p, int v) {
		if (p == 0) {
			p = ++pool;
			bst[p].val = v;
			bst[p].rpt = 1;
			bst[p].size = 1;
			return;
		}

		bst[p].size++;
		if (v == bst[p].val) bst[p].rpt++;
		else if (v > bst[p].val) {
			insert(bst[p].right, v);
			maintain(p, 0);
		} else {
			insert(bst[p].left, v);
			maintain(p, 1);
		}
	}

	void del(int &p, int v) {
		bst[p].size--;
		if (bst[p].val == v) {
			if (bst[p].rpt > 1) {
				bst[p].rpt--;
				return;
			}

			if (bst[p].left == 0 && bst[p].right == 0) {
				p = 0;
				return;
			}

			if (bst[p].left == 0 || bst[p].right == 0) {
				p = bst[p].left + bst[p].right;
				return;
			}

			int t = bst[p].right;
			while (bst[t].left)
				t = bst[t].left;

			bst[p].val = bst[t].val;
			bst[p].rpt = bst[t].rpt;
			bst[t].rpt = 1;
			del(bst[p].right, bst[t].val);
			return;
		}

		if (v > bst[p].val) del(bst[p].right, v);
		else del(bst[p].left, v);
	}

	int rank(int p, int v) {
		if (p == 0) return 0;
		if (v == bst[p].val) return bst[bst[p].left].size + 1;
		else if (v > bst[p].val) return bst[bst[p].left].size + bst[p].rpt + rank(bst[p].right, v);
		else return rank(bst[p].left, v);
	}

	int find(int p, int r) {
		if (p == 0) return 0;
		if (r <= bst[bst[p].left].size) return find(bst[p].left, r);
		if (r <= bst[bst[p].left].size + bst[p].rpt) return bst[p].val;
		else return find(bst[p].right, r - bst[bst[p].left].size - bst[p].rpt);
	}

	int pre(int p, int v) {
		if (p == 0) return 0;
		if (v <= bst[p].val) return pre(bst[p].left, v);
		int t = pre(bst[p].right, v);
		if (t == 0) return bst[p].val;
		else return t;
	}

	int post(int p, int v) {
		if (p == 0) return 0;
		if (v >= bst[p].val) return post(bst[p].right, v);
		int t = post(bst[p].left, v);
		if (t == 0) return bst[p].val;
		else return t;
	}
} sbt;

int getint()
{
	register int x = 0;
	register char ch = 0;
	char f = 0;
	while (!isdigit(ch)) f = (ch == '-'), ch = getchar();
	while (isdigit(ch)) x = (x << 1) + (x << 3) + (ch ^ 0x30), ch = getchar();
	return f ? -x : x;
}

int main()
{
	freopen("t.in", "r", stdin);
	freopen("test.txt", "w", stdout);
	int n = getint();
	int t;

	for (int i = 1; i <= n; i++) {
		int opt, x;
		opt = getint(); x = getint();
		if (opt == 1) sbt.insert(sbt.root, x);
		else if (opt == 2) sbt.del(sbt.root, x);
		else if (opt == 3) printf("%d\n", t = sbt.rank(sbt.root, x));
		else if (opt == 4) printf("%d\n", t = sbt.find(sbt.root, x));
		else if (opt == 5) printf("%d\n", t = sbt.pre(sbt.root, x));
		else if (opt == 6) printf("%d\n", t = sbt.post(sbt.root, x));
		if (t == 247798) printf("here: %d %d\n", opt, x);
	}

	return 0;
}