记录编号	357395	评测结果	AAAAAAAAAA
题目名称	[Tyvj 1728]普通平衡树	最终得分	100
用户昵称	Hzoi_Go灬Fire	是否通过	通过
代码语言	C++	运行时间	0.257 s
提交时间	2016-12-11 07:04:19	内存使用	3.34 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=100000*2;
#define LL long long
#define Inf 2e9
#define Begin freopen("phs.in","r",stdin);freopen("phs.out","w",stdout);
#define End fclose(stdin);fclose(stdout);
int RT;
struct SBT{
	int size[maxn],ls[maxn],rs[maxn],v[maxn],cnt;
	void pushup(int rt){size[rt]=size[ls[rt]]+size[rs[rt]]+1;}
	void Turn_right(int & rt){//右旋 
		//把rt的左子树变成左儿子的右子树，rt成为左儿子的右儿子 
		int t=ls[rt];
		ls[rt]=rs[t];pushup(rt);
		rs[t]=rt;pushup(t);
		rt=t; 
	}
	void Turn_left(int & rt){//左旋 
		//把rt的右子树变成右儿子的左子树，rt成为右儿子的左儿子
		int t=rs[rt];
		rs[rt]=ls[t];pushup(rt);
		ls[t]=rt;pushup(t);
		rt=t;
	}
	#define Balance_all Balance(rt);Balance(ls[rt]);Balance(rs[rt]);
	void Balance(int & rt){
		if(size[ls[ls[rt]]]>size[rs[rt]]){
			Turn_right(rt);Balance_all;return;
		}
		if(size[rs[rs[rt]]]>size[ls[rt]]){
			Turn_left(rt);Balance_all;return;
		}
		if(size[rs[ls[rt]]]>size[rs[rt]]){
			Turn_left(ls[rt]);Turn_right(rt);Balance_all;return;
		}
		if(size[ls[rs[rt]]]>size[ls[rt]]){
			Turn_right(rs[rt]);Turn_left(rt);Balance_all;return;
		}
	}
	#undef Balance_all
	void Insert(int & rt,int date){
		if(rt==0){
			rt=++cnt;size[rt]=1;v[rt]=date;return;
		}
		if(date<v[rt])Insert(ls[rt],date);
		else Insert(rs[rt],date);
		pushup(rt);Balance(rt);
	}
	void Del(int & rt,int date){
		if(v[rt]==date){
			if(ls[rt]==0 && rs[rt]==0){rt=0;return;}
			if(ls[rt]==0){rt=rs[rt];return;}
			if(rs[rt]==0){rt=ls[rt];return;}
			Turn_right(rt);Del(rs[rt],date);pushup(rt);
			return;
		}
		if(v[rt]<date)Del(rs[rt],date);
		else Del(ls[rt],date);
		pushup(rt);Balance(rt);
	}
	int Get_prev(int rt,int date){
		if(rt==0)return -Inf;
		if(v[rt]<date)return max(v[rt],Get_prev(rs[rt],date));
		else return Get_prev(ls[rt],date);
	}
	int Get_succ(int rt,int date){
		if(rt==0)return Inf;
		if(v[rt]>date)return min(v[rt],Get_succ(ls[rt],date));
		else return Get_succ(rs[rt],date);
	}
	int Get_date(int rt,int th){
		if(size[ls[rt]]+1==th)return v[rt];
		if(size[ls[rt]]+1>th)return Get_date(ls[rt],th);
		else return Get_date(rs[rt],th-size[ls[rt]]-1);
	}
	int Get_th(int rt,int date){
		if(rt==0)return Inf;
		if(v[rt]==date)return min(size[ls[rt]]+1,Get_th(ls[rt],date));
		if(v[rt]>date)return Get_th(ls[rt],date);
		else return size[ls[rt]]+1+Get_th(rs[rt],date);
	}
}T;
int n;
void Init();

int main(){
	Begin;
    Init();
    getchar();getchar();
    End;
	return 0;
}
void Init(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		int type,date;scanf("%d%d",&type,&date);
		if(type==1)T.Insert(RT,date);
		else if(type==2)T.Del(RT,date);
		else if(type==3)printf("%d\n",T.Get_th(RT,date));
		else if(type==4)printf("%d\n",T.Get_date(RT,date));
		else if(type==5)printf("%d\n",T.Get_prev(RT,date));
		else if(type==6)printf("%d\n",T.Get_succ(RT,date));
	}
}