记录编号	584039	评测结果	AAAAAAAAAA
题目名称	[Tyvj 1728]普通平衡树	最终得分	100
用户昵称	┭┮﹏┭┮	是否通过	通过
代码语言	C++	运行时间	0.213 s
提交时间	2023-10-27 18:16:13	内存使用	7.98 MiB

#include <bits/stdc++.h> 
using namespace std;
const int N = 1e5+10;
int n;
struct made{
	int ls,rs;//左右儿子(ps:下次一定不能加s太麻烦了) 
	int val,dat;// 
	int cnt,size;
}t[N];
int tot,root,INF = 1e9;

int add(int x){
	tot++;
	t[tot].val = x,t[tot].dat = rand();
	t[tot].cnt = t[tot].size = 1;
	return tot;
}
void pushup(int p){
	t[p].size = t[t[p].ls].size + t[t[p].rs].size + t[p].cnt;
}
void zip(int &p){
	int q = t[p].ls;
	t[p].ls = t[q].rs;t[q].rs = p;p = q;
	pushup(t[p].rs);pushup(p);//
}
void zap(int &p){
	int q = t[p].rs;
	t[p].rs = t[q].ls;t[q].ls = p;p = q;
	pushup(t[p].ls);
	pushup(p);//
}
void build(){
	add(-INF),add(INF);
	root = 1;
	t[1].rs = 2;pushup(root);
}//
//
void insert(int &p,int x){
	if(p == 0){
		p = add(x);
		return;
	}
	if(t[p].val == x){
		t[p].cnt++;pushup(p);//错误 
		return;
	}
	else if(x < t[p].val){
		insert(t[p].ls,x);
		if(t[p].dat < t[t[p].ls].dat)zip(p);
	}
	else{
		insert(t[p].rs,x);
		if(t[p].dat < t[t[p].rs].dat)zap(p);
	}
	pushup(p);
}
void del(int &p,int x){
	if(p == 0)return;
	if(t[p].val == x){
		if(t[p].cnt > 1){
			t[p].cnt--;pushup(p) ;//错误 
			return;
		}
		if(t[p].ls || t[p].rs){
			if(!t[p].rs || t[t[p].ls].dat > t[t[p].rs].dat)zip(p),del(t[p].rs,x);
			else zap(p),del(t[p].ls,x);
			pushup(p);
		}
		else p = 0;
		return;
	}
	x < t[p].val ? del(t[p].ls,x):del(t[p].rs,x);
	pushup(p);
}
int getp(int p,int x){
	if(p == 0)return INF;
	if(x <= t[t[p].ls].size)return getp(t[p].ls,x);
	else if(x <= t[t[p].ls].size + t[p].cnt)return t[p].val;
	return getp(t[p].rs,x - t[t[p].ls].size - t[p].cnt);
}
int getd(int p,int x){
	if(p == 0)return 0;
	if(x == t[p].val)return t[t[p].ls].size + 1;
	if(x < t[p].val)return getd(t[p].ls,x);
	return t[t[p].ls].size + t[p].cnt + getd(t[p].rs,x);
}
int getpre(int x){
	int ans = 1,p = root;
	while(p){
		if(t[p].val == x){
			if(t[p].ls){
				p = t[p].ls;
				while(t[p].rs)p = t[p].rs;
				ans = p;
			}
			break;
		}
		if(t[p].val < x && t[p].val > t[ans].val)ans = p;
		p = x < t[p].val ? t[p].ls:t[p].rs; 
	}
	return t[ans].val;
}
int getnx(int x){
	int ans = 2,p = root;
	while(p){
		if(t[p].val == x){
			if(t[p].rs){
				p = t[p].rs;
				while(t[p].ls)p = t[p].ls;
				ans = p;
			}
			break;
		}
		if(t[p].val > x && t[p].val < t[ans].val)ans = p;
		p = x < t[p].val ? t[p].ls:t[p].rs;
	}
	return t[ans].val;
}
int main(){
	freopen("phs.in","r",stdin);
	freopen("phs.out","w",stdout);
    build();
	scanf("%d",&n);
	while(n--){
		int op,x;
		scanf("%d%d",&op,&x);
		switch(op){
			case 1:
				insert(root,x);
				break;
			case 2:
				del(root,x);
				break;
			case 3:
				printf("%d\n",getd(root,x)-1);// 
				break;
			case 4:
				printf("%d\n",getp(root,x+1));//建树时多加入了两个节点 
				break;
			case 5:
				printf("%d\n",getpre(x));
				break;
			case 6:
				printf("%d\n",getnx(x));
				break;
		}
	}
	
	return 0;
	
}