玄关球条

#include <bits/stdc++.h>
using namespace std;
template <typename T>
class Splay 
{
public:
	struct Node 
	{
		int fa, sz, cnt, ch[2];
		T val;
	};
	vector<Node> t;
	int root;
	Splay()
	{
		root = 0;
		t.push_back({0, 0, 0, {0, 0}, 0});
	}
	~Splay()
	{
		t.clear();
	}
	int newnode(T v)
	{
		t.push_back({0, 1, 1, {0, 0}, v});
		return t.size()-1;
	}
	void pushup(int p)
	{
		if (!p)
			return ;
		t[p].sz = t[p].cnt;
		if (t[p].ch[0] != 0)
		{
			t[p].sz += t[t[p].ch[0]].sz;
		}
		if (t[p].ch[1] != 0)
		{
			t[p].sz += t[t[p].ch[1]].sz;
		}
		return ;
	}
	int get(int p)
	{
		return (t[t[p].fa].ch[1] == p);
	}
	void rotate(int p)
	{
		if (!p)
			return ;
		int father = t[p].fa, grand_father = t[father].fa;
		int tmp = get(p);
		t[father].ch[tmp] = t[p].ch[tmp ^ 1];
		t[t[p].ch[tmp ^ 1]].fa = father;
		t[p].ch[tmp ^ 1] = father;
		t[father].fa = p;
		if (grand_father != 0)
		{
			if (t[grand_father].ch[0] == father)
			{
				t[grand_father].ch[0] = p;
			}
			else 
			{
				t[grand_father].ch[1] = p;
			}
		}
		t[p].fa = grand_father;
		pushup(father);
		pushup(p);
	}
	void splay(int p, int goal = 0)
	{
		if (!p)
			return ;
		while (t[p].fa != goal)
		{
			if (t[t[p].fa].fa != goal)
			{
				if (get(p) == get(t[p].fa))
				{
					rotate(t[p].fa);
				}
				else rotate(p);
			}
			rotate(p);
		}
		if (goal == 0)
		{
			root = p;
		}
	}
	int insert(T v)
	{
		if (root == 0)
		{
			root = newnode(v);
			return root;
		}
		int p = root;
		while (p)
		{
			if (t[p].val == v)
			{
				t[p].cnt++;
				pushup(p);
				splay(p);
				return p;
			}
			int lst = p;
			if (v < t[p].val)
				p = t[p].ch[0];
			else p = t[p].ch[1];
			if (p == 0)
			{
				int tmp = newnode(v);
				t[lst].ch[(v < t[lst].val ? 0 : 1)] = tmp;
				t[tmp].fa = lst;
				pushup(lst);
				splay(tmp);
				return tmp;
			}
		}
		return -1;
	}
	int find(T v)
	{
		int ans = 0, p = root;
		while (p)
		{
			if (v < t[p].val)
				p = t[p].ch[0];
			else 
			{
				if (t[p].ch[0] != 0)
					ans += t[t[p].ch[0]].sz;
				if (t[p].val == v)
				{
					splay(p);
					return ans+1;
				}
				else 
				{
					ans += t[p].cnt;
					p = t[p].ch[1];
				}
			}
		}
		return ans+1;
	}
	void print(int p)
	{
		if (!p)
			return ;
		print(t[p].ch[0]);
		for (int i=1;i<=t[p].cnt;i++)
			cout << t[p].val << " ";
		print(t[p].ch[1]);
	}
	int underlying_pre(T v)
	{
		find(v);
		int p = t[root].ch[0];
		while (t[p].ch[1])
			p = t[p].ch[1];
		return p;
	}
	T pre(T v)
	{
		find(v);
		int p = t[root].ch[0];
		while (t[p].ch[1])
			p = t[p].ch[1];
		return t[p].val;
	}
	T nxt(T v)
	{
		find(v);
		int p = t[root].ch[1];
		while (t[p].ch[0])
			p = t[p].ch[0];
		return t[p].val;
	}
	int kth(int k)
	{
		int p = root;
		while (p && k)
		{
			if (t[p].ch[0] && t[t[p].ch[0]].sz >= k)
			{
				p = t[p].ch[0];
			}
			else 
			{
				int tmp = t[p].cnt;
				if (t[p].ch[0])
					tmp += t[t[p].ch[0]].sz;
				if (k <= tmp)
				{
					splay(p);
					return t[p].val;
				}
				k -= tmp;
				p = t[p].ch[1];
			}
		}
		return -1;
	}
	void clear(int p)
	{
		t[p] = {0, 0, 0, {0, 0}, 0};
		return ;
	}
	void del(T v)
	{
		find(v);
		if (t[root].cnt > 1)
		{
			t[root].cnt--;
			pushup(root);
			return ;
		}
		else if (t[root].ch[0] == 0 && t[root].ch[1] == 0)
		{
			clear(root);
			root = 0;
			return ;
		}
		else if (t[root].ch[0] == 0)
		{
			int tmp = t[root].ch[1];
			clear(root);
			root = tmp;
		}
		else if (t[root].ch[1] == 0)
		{
			int tmp = t[root].ch[0];
			clear(root);
			root = tmp;
		}
		else
		{
			int old = root, new_ = underlying_pre(v);
			splay(new_);
			t[new_].ch[1] = t[old].ch[1];
			t[t[old].ch[1]].fa = new_;
			clear(old);
			pushup(t[new_].ch[1]);
			pushup(new_);
			root = new_;
			return ;
		}
	}
};
signed main()
{
//	ios::sync_with_stdio(false);
//	cin.tie(0), cout.tie(0);
	int n;
	cin >> n;
	Splay<int> t;
	while (n--)
	{
		int opt, x;
		cin >> opt >> x;
		if (opt == 1)
		{
			t.insert(x);
		}
		else if (opt == 2)
		{
			t.del(x);
		}
		else if (opt == 3)
		{
			cout << t.find(x) << "\n";
		}
		else if (opt == 4)
		{
			cout << t.kth(x) << '\n';
		}
		else if (opt == 5)
		{
			t.insert(x);
			cout << t.pre(x) << '\n';
			t.del(x);
		}
		else
		{
			t.insert(x);
			cout << t.nxt(x) << '\n';
			t.del(x);
		}
//		cout << '\n';
//		t.print(t.root);
//		cout << '\n';
	}
	return 0;
}