记录编号	590758	评测结果	AAAAAAAAAA
题目名称	[Tyvj 1728]普通平衡树	最终得分	100
用户昵称	yrtiop	是否通过	通过
代码语言	C++	运行时间	0.514 s
提交时间	2024-07-11 11:06:38	内存使用	5.35 MiB

// 大家好啊，今天来点大家想看的东西啊。
#include <bits/stdc++.h>
#define pb emplace_back
#define fir first
#define sec second

using i64 = long long;
using u32 = unsigned;
using pii = std::pair<int, int>;
constexpr int maxn = 1e5 + 5;
std::mt19937 rd((unsigned)time(0));

struct node {
	int ls, rs, val, siz;
	u32 key;
	node() { ls = rs = val = key = siz = 0; }
	node(int ls, int rs, int val, u32 key, int siz) : ls(ls), rs(rs), val(val), key(key), siz(siz) {}
} tr[maxn];

int num, rt;

int NewNode(int x) {
	return tr[++num] = node(0, 0, x, rd(), 1), num;
}

void pushup(int x) {
	return tr[x].siz = tr[tr[x].ls].siz + tr[tr[x].rs].siz + 1, void();
}

void split(int p, int val, int& x, int& y) {
	if (!p) return x = y = 0, void();
	if (tr[p].val <= val) {
		x = p;
		split(tr[x].rs, val, tr[x].rs, y);
	} else {
		y = p;
		split(tr[y].ls, val, x, tr[y].ls);
	}
	return pushup(p);
}

int merge(int x, int y) {
	if (!x || !y) return x | y;
	if (tr[x].key <= tr[y].key) {
		tr[x].rs = merge(tr[x].rs, y);
		return pushup(x), x;
	} else {
		tr[y].ls = merge(x, tr[y].ls);
		return pushup(y), y;
	}
}

void insert(int x) {
	int a, b, c;
	split(rt, x, a, c);
	b = NewNode(x);
	return rt = merge(a, merge(b, c)), void();
}

void remove(int x) {
	int a, b, c;
	split(rt, x, b, c), split(b, x - 1, a, b);
	return rt = merge(a, merge(merge(tr[b].ls, tr[b].rs), c)), void();
}

int findrk(int x) {
	int a, b, r;
	split(rt, x - 1, a, b);
	r = tr[a].siz + 1;
	return rt = merge(a, b), r;
}

void splitrk(int p, int rk, int& x, int& y) {
	if (!p) return x = y = 0, void();
	if (tr[tr[p].ls].siz + 1 <= rk) {
		x = p;
		splitrk(tr[p].rs, rk - 1 - tr[tr[p].ls].siz, tr[x].rs, y);
	} else {
		y = p;
		splitrk(tr[p].ls, rk, x, tr[y].ls);
	}
	return pushup(p);
}

int findval(int k) {
	int a, b;
	splitrk(rt, k, a, b);
	int tmp = a;
	while (tr[tmp].rs) tmp = tr[tmp].rs;
	tmp = tr[tmp].val;
	return rt = merge(a, b), tmp;
}

int precur(int x) {
	return findval(findrk(x) - 1);
}

int suffix(int x) {
	return findval(findrk(x + 1));
}

int main() {
	freopen("phs.in", "r", stdin);
	freopen("phs.out", "w", stdout);
	std::cin.tie(nullptr)->sync_with_stdio(false);
	int n;
	std::cin >> n;
	while (n--) {
		int opt, x;
		std::cin >> opt >> x;
		if (opt == 1) {
			insert(x);
		} else if (opt == 2) {
			remove(x);
		} else if (opt == 3) {
			std::cout << findrk(x) << '\n';
		} else if (opt == 4) {
			std::cout << findval(x) << '\n';
		} else if (opt == 5) {
			std::cout << precur(x) << '\n';
		} else {
			std::cout << suffix(x) << '\n';
		}
	}
	return 0;
}