平衡树板子

//12252024832524
#include <cstdio>
#include <cstring>
#include <algorithm>
#define TT template<typename T>
using namespace std; 

typedef long long LL;
const int MAXN = 100005;
const int MOD = 998244353;
int n;

LL Read()
{
	LL x = 0,f = 1;char c = getchar();
	while(c > ‘9‘ || c < ‘0‘){if(c == ‘-‘)f = -1;c = getchar();}
	while(c >= ‘0‘ && c <= ‘9‘){x = (x*10) + (c^48);c = getchar();}
	return x * f;
}
TT void Put1(T x)
{
	if(x > 9) Put1(x/10);
	putchar(x%10^48);
}
TT void Put(T x,char c = -1)
{
	if(x < 0) putchar(‘-‘),x = -x;
	Put1(x); if(c >= 0) putchar(c);
}
TT T Max(T x,T y){return x > y ? x : y;}
TT T Min(T x,T y){return x < y ? x : y;}
TT T Abs(T x){return x < 0 ? -x : x;}

int tot,rt;
struct FHQ_Treap
{
	int l,r,val,rd,siz;
}t[MAXN];
void up(int x){t[x].siz = t[t[x].l].siz + t[t[x].r].siz + 1;}
void split(int now,int val,int &x,int &y)
{
	if(!now) {x = y = 0;return;}
	else
	{
		if(t[now].val <= val) x = now,split(t[now].r,val,t[now].r,y);
		else y = now,split(t[now].l,val,x,t[now].l);
		up(now);
	}
}
int mge(int x,int y)
{
	if(!x || !y) return x|y;
	if(t[x].rd < t[y].rd) {t[x].r = mge(t[x].r,y);up(x);return x;}
	else {t[y].l = mge(x,t[y].l);up(y);return y;}
}
int newnode(int val)
{
	t[++tot] = {0,0,val,rand(),1};
	return tot;
}
int x,y,z;
void ins(int val)
{
//	printf("ins ins ins\n");
	split(rt,val-1,x,y);
//	printf("ins %d %d\n",x,y);
	rt = mge(x,mge(newnode(val),y));
}
void del(int val)
{
	split(rt,val,x,z);
	split(x,val-1,x,y);
	rt = mge(mge(x,mge(t[y].l,t[y].r)),z);
}
int qrk(int val)
{
	split(rt,val-1,x,y);
	int ret = t[x].siz+1;
	rt = mge(x,y);
	return ret;
}
int qval(int rk)
{
	x = rt;
	while(1)
	{
		if(t[t[x].l].siz+1 == rk) return t[x].val;
		else if(t[t[x].l].siz >= rk) x = t[x].l;
		else rk -= t[t[x].l].siz+1,x = t[x].r;
	}
}
int pre(int val)
{
	split(rt,val-1,x,y);
	int now = x;
	while(t[now].r) now = t[now].r;
	rt = mge(x,y);
	return t[now].val;
}
int suf(int val)
{
	split(rt,val,x,y);
	int now = y;
	while(t[now].l) now = t[now].l;
	rt = mge(x,y);
	return t[now].val;
}
void dfs(int now)
{
	if(!now) return;
//	printf("dfs %d %d %d %d\n",now,t[now].val,t[now].l,t[now].r);
	dfs(t[now].l);
	dfs(t[now].r);
}

int main()
{
//	freopen(".in","r",stdin);
//	freopen(".out","w",stdout);
	srand(42523);
	for(int T = Read(); T ;-- T)
	{
		int opt = Read();
		if(opt == 1) ins(Read());
		else if(opt == 2) del(Read());
		else if(opt == 3) Put(qrk(Read()),‘\n‘);
		else if(opt == 4) Put(qval(Read()),‘\n‘);
		else if(opt == 5) Put(pre(Read()),‘\n‘);
		else if(opt == 6) Put(suf(Read()),‘\n‘);
	}
	return 0;
}