记录编号	575650	评测结果	AAAAAAAAAA
题目名称	[Tyvj 1728]普通平衡树	最终得分	100
用户昵称	yrtiop	是否通过	通过
代码语言	C++	运行时间	0.285 s
提交时间	2022-09-25 09:23:59	内存使用	3.82 MiB

// Problem: P3369 【模板】普通平衡树
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3369
// Memory Limit: 128 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>

const int maxn = 1e5 + 5;
int sz,rt,size[maxn],son[maxn][2],rnd[maxn],val[maxn];

int newnode(int k) {
	size[++ sz] = 1;
	rnd[sz] = rand();
	son[sz][0] = son[sz][1] = 0;
	val[sz] = k;
	return sz;
}

void pushup(int x) {
	size[x] = size[son[x][0]] + size[son[x][1]] + 1;
	return ;
}

void split(int now,int k,int& x,int& y) {
	if(!now) {
		x = y = 0;
		return ;
	}
	if(val[now] <= k) {
		x = now;
		split(son[now][1] , k , son[now][1] , y);
		pushup(x);
		return ;
	}
	else {
		y = now;
		split(son[now][0] , k , x , son[now][0]);
		pushup(y);
		return ;
	}
	pushup(now);
	return ;
}

int merge(int x,int y) {
	if(!x||!y)return x | y;
	if(rnd[x] < rnd[y]) {
		son[x][1] = merge(son[x][1] , y);
		pushup(x);
		return x;
	}
	else {
		son[y][0] = merge(x , son[y][0]);
		pushup(y);
		return y;
	}
}

void insert(int k) {
	int x = 0,y = 0;
	split(rt , k , x , y);
	rt = merge(merge(x , newnode(k)) , y);
	return ;
}

void remove(int k) {
	int x = 0,y = 0,z = 0;
	split(rt , k - 1 , x , y);
	split(y , k , y , z);
	if(y)y = merge(son[y][0] , son[y][1]);
	rt = merge(merge(x , y) , z);
	return ;
}

int findrank(int k) {
	int x = 0,y = 0;
	split(rt , k - 1 , x , y);
	int ans = size[x] + 1;
	rt = merge(x , y);
	return ans;
}

int findval(int now,int k) {
	while(true) {
		if(k <= size[son[now][0]])now = son[now][0];
		else if(k == size[son[now][0]] + 1)return now;
		else k -= size[son[now][0]] + 1,now = son[now][1];
	}
}

int precur(int k) {
	int x = 0,y = 0;
	split(rt , k - 1 , x , y);
	int ans = val[findval(x , size[x])];
	rt = merge(x , y);
	return ans;
}

int suffix(int k) {
	int x = 0,y = 0;
	split(rt , k , x , y);
	int ans = val[findval(y , 1)];
	rt = merge(x , y);
	return ans;
}

int main() {
	freopen("phs.in","r",stdin);
	freopen("phs.out","w",stdout);
	int n;
	scanf("%d",&n);
	rt = sz = 0;
	while(n --) {
		int op,k;
		scanf("%d %d",&op,&k);
		switch(op) {
			case 1: {
				insert(k);
				break ;
			}
			case 2: {
				remove(k);
				break ;
			}
			case 3: {
				printf("%d\n",findrank(k));
				break ;
			}
			case 4: {
				printf("%d\n",val[findval(rt , k)]);
				break ;
			}
			case 5: {
				printf("%d\n",precur(k));
				break ;
			}
			case 6: {
				printf("%d\n",suffix(k));
				break ;
			}
		}
	}
	return 0;
}