{1,2,3,4,5}

0的前驱是谁？5的后缀是谁？

#include <bits/stdc++.h>
using namespace std;
const int maxn = 100100,INF = 10000010;
inline void read(int& x){
	int y = 0,w = 1;
	char ch = getchar();
	while(ch < '0' || ch > '9'){if(ch == '-') w = -1;ch = getchar();}
	while(ch >= '0' && ch <= '9'){y = y * 10 + ch - '0';ch = getchar();}
	x = y * w;
}
void write(int x){
	if(x < 0) x=-x,putchar('-');
	if(x > 9) write(x/10);
	putchar(x%10+'0');
}
int n,tot,root;
struct node{
	int l,r;
	int cnt,siz,vlu,rnd;
}t[maxn];
inline int creat(int vlu){
	t[++tot].vlu = vlu;
	t[tot].cnt = t[tot].siz = 1;
	t[tot].rnd = rand();
	return tot;
}
inline void update(int p){t[p].siz = t[t[p].l].siz + t[t[p].r].siz + t[p].cnt;}
inline void zig(int& p){//左儿子向右转  
	int q = t[p].l;
	t[p].l = t[q].r,t[q].r = p;
	p = q;
	update(t[p].r),update(p);
}
inline void zag(int& p){//右儿子向左转 
	int q = t[p].r;
	t[p].r = t[q].l,t[q].l = p;
	p = q;
	update(t[p].l),update(p);
}
void insert(int& p,int vlu){
	if(!p){
		p = creat(vlu);
		return;
	}
	if(vlu == t[p].vlu){
		t[p].cnt++;
		update(p);
		return;
	}
	if(vlu > t[p].vlu){
		insert(t[p].r,vlu);
		if(t[p].rnd < t[t[p].r].rnd) zag(p);//注意判断 是否需要旋转 
	}
	if(vlu < t[p].vlu){
		insert(t[p].l,vlu);
		if(t[p].rnd < t[t[p].l].rnd) zig(p);
	}
	update(p);
	return;
}
void cut(int& p,int vlu){
	if(!p) return;
	if(vlu == t[p].vlu){
		if(t[p].cnt > 1){
			t[p].cnt--;
			update(p);//注意这里要更新一下 
			return;
		}
		if(t[p].l || t[p].r){//不是叶子节点 先旋转 
			if(!t[p].r || t[t[p].l].rnd > t[t[p].r].rnd) zig(p),cut(t[p].r,vlu);//p变成它曾经左儿子的右儿子 
			else zag(p),cut(t[p].l,vlu);//不直接删除 是因为无法确定旋转顺序 
		}
		else p = 0;
		return;
	}
	if(vlu < t[p].vlu) cut(t[p].l,vlu);
	else cut(t[p].r,vlu);
	update(p);
	return;
}
int getrankbyvlu(int p,int vlu){
	if(!p) return 0;
	if(vlu == t[p].vlu) return t[t[p].l].siz;//
	if(vlu < t[p].vlu) return getrankbyvlu(t[p].l,vlu);//
	else return getrankbyvlu(t[p].r,vlu) + t[t[p].l].siz + t[p].cnt;//
}
int getvlubyrank(int p,int rank){
	if(!p) return INF;
	if(t[t[p].l].siz >= rank) return getvlubyrank(t[p].l,rank);//t[t[p].l].siz >= rank
	else if(t[t[p].l].siz + t[p].cnt < rank) return getvlubyrank(t[p].r,rank - t[t[p].l].siz - t[p].cnt);
	//not <= 
	else return t[p].vlu;//
}
int getpre(int vlu){
	int res = -INF;
	int p = root;
	while(p){
		if(vlu == t[p].vlu){
			if(t[p].l){
				p = t[p].l;
				while(t[p].r) p = t[p].r;
				res = t[p].vlu;
			}
			return res;
		}
		if(t[p].vlu < vlu && t[p].vlu > res) res = t[p].vlu;//有可能 vlu 并不在原序列出现 所以更新 
		if(vlu < t[p].vlu) p = t[p].l;
		if(vlu > t[p].vlu) p = t[p].r;
	}
	return res;
}
int getnxt(int vlu){
	int res = INF;
	int p = root;
	while(p){
		if(vlu == t[p].vlu){
			if(t[p].r){
				p = t[p].r;
				while(t[p].l) p = t[p].l;
				res = t[p].vlu;
			}
			return res;
		}
		if(t[p].vlu > vlu && t[p].vlu < res) res = t[p].vlu;//有可能 vlu 并不在原序列出现 所以更新 
		if(vlu < t[p].vlu) p = t[p].l;
		if(vlu > t[p].vlu) p = t[p].r;
	}
	return res;
}
int main(){	
//	freopen("P3369_5.in","r",stdin);
	read(n);
	int opt,x;
	while(n--){
		read(opt),read(x);
		if(opt == 1) insert(root,x);
		if(opt == 2) cut(root,x);
		if(opt == 3) write(getrankbyvlu(root,x) + 1),putchar('\n');
		if(opt == 4) write(getvlubyrank(root,x)),putchar('\n');
		if(opt == 5) write(getpre(x)),putchar('\n');
		if(opt == 6) write(getnxt(x)),putchar('\n');
	}
	return 0;
}