记录编号	145358	评测结果	AAAAAAAAAA
题目名称	[Tyvj 1728]普通平衡树	最终得分	100
用户昵称	Asm.Def	是否通过	通过
代码语言	C++	运行时间	0.133 s
提交时间	2015-01-07 22:41:46	内存使用	9.85 MiB

/*====================Asm.Def========================*/
#include <iostream>
#include <cctype>
#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <ctime>
#include <queue>
using namespace std;
char *in = (char*)malloc(10000000);
inline void getd(int &x){
	char c = *(in++);
	bool minus = 0;
	while(!isdigit(c) && c != '-')c = *(in++);
	if(c == '-')minus = 1, c = *(in++);
	x = c - '0';
	while(isdigit(c = *(in++)))x = x * 10 + c - '0';
	if(minus)x = -x;
}
/*======================================================*/
#define SIZE(o) ( o == NULL ? 0 : o->size )
int n;
//Size_Balanced_Tree
struct Size_Balanced_Tree{
	int val, size, cnt;
	Size_Balanced_Tree *son[2];
	Size_Balanced_Tree(int x):val(x),size(1),cnt(1){son[0] = son[1] = NULL;}
	inline void update(){size = SIZE(son[0]) + SIZE(son[1]) + cnt;}
}*Root;

inline void rot(Size_Balanced_Tree* &o, bool lr){//将lr方向的子树旋转到o的位置
	Size_Balanced_Tree *t = o->son[lr];
	o->son[lr] = t->son[lr^1]; t->son[lr^1] = o; o = t;
	o->son[lr^1]->update(), o->update();
}

inline void Maintain(Size_Balanced_Tree* &o){
	if(o->son[0] == NULL && o->son[1] == NULL)return;
	if(o->son[0] == NULL){
		if(o->son[1]->son[0]!=NULL || o->son[1]->son[1]!=NULL)
			rot(o, 1);
		return;
	}
	if(o->son[1] == NULL){
		if(o->son[0]->son[0]!=NULL || o->son[0]->son[1]!=NULL)
			rot(o, 0);
		return;
	}
	if(o->son[0]->size < max(SIZE(o->son[1]->son[0]), SIZE(o->son[1]->son[1])))
		rot(o, 1);
	else if(o->son[1]->size < max(SIZE(o->son[0]->son[0]), SIZE(o->son[0]->son[1])))
		rot(o, 0);
}

inline void insert(Size_Balanced_Tree* &o, int x){
	if(o == NULL){
		o = new Size_Balanced_Tree(x);
		return;
	}
	if(x < o->val){//left
		insert(o->son[0], x);
		++o->size;
		Maintain(o);
		return;
	}
	if(x > o->val){//right
		insert(o->son[1], x);
		++o->size;
		Maintain(o);
		return;
	}
	++o->size; ++o->cnt;//same
}
inline int getrank(Size_Balanced_Tree* &o, int x){
	if(o->val == x) return SIZE(o->son[0]) + 1;
	if(x < o->val) return getrank(o->son[0], x);
	return SIZE(o->son[0]) + o->cnt + getrank(o->son[1], x);
}
inline void del(Size_Balanced_Tree* &o, int x){
	if(x == o->val){
		if(o->cnt > 1){--o->cnt;--o->size;return;}
		int k = 0;
		bool ok = 0, lr;
		if(o->son[0] != NULL)k = o->son[0]->size, ok = 1, lr = 0;
		if(o->son[1] != NULL && o->son[1]->size > k)ok = 1, lr = 1;
		if(!ok){
			delete o;o = NULL;
			return;
		}
		rot(o, lr); del(o->son[lr^1], x);
		o->update();
		return;
	}
	if(x < o->val){
		del(o->son[0], x);
		o->update();
	}
	else{
		del(o->son[1], x);
		o->update();
	}
}
inline int getx(Size_Balanced_Tree* o, int k){
	int lsize = SIZE(o->son[0]);
	if(k <= lsize)return getx(o->son[0], k);
	if(k - lsize <= o->cnt)return o->val;
	return getx(o->son[1], k - lsize - o->cnt);
}
inline int prev(Size_Balanced_Tree* &o, int x, bool &t){
	if(o->val == x){
		if(o->son[0] != NULL){
			t = 1;
			return getx(o->son[0], o->son[0]->size);
		}
		t = 0;return 0;
	}
	if(x > o->val){
		if(o->son[1] == NULL){t = 1; return o->val;}
		int k = prev(o->son[1], x, t);
		if(t)return k;
		t = 1; return o->val;
	}
	if(o->son[0] != NULL)return prev(o->son[0], x, t);
	t = 0; return 0;
}
inline int next(Size_Balanced_Tree* &o, int x, bool &t){
	if(o->val == x){
		if(o->son[1] != NULL){
			t = 1;
			return getx(o->son[1], 1);
		}
		t = 0;return 0;
	}
	if(x < o->val){
		if(o->son[0] == NULL){t = 1; return o->val;}
		int k = next(o->son[0], x, t);
		if(t)return k;
		t = 1; return o->val;
	}
	if(o->son[1] != NULL) return next(o->son[1], x, t);
	t = 0;return 0;
}
//Size_Balanced_Tree

int main(){
	#if defined DEBUG
	freopen("test", "r", stdin);
	#else
	freopen("phs.in", "r", stdin);
	freopen("phs.out", "w", stdout);
	#endif

	fread(in, 1, 10000000, stdin);
	
	getd(n);
	int opt, x;
	bool t;
	while(n--){
		getd(opt), getd(x);
		switch(opt){
			case 1: insert(Root, x);break;
			case 2: del(Root, x);break;
			case 3: printf("%d\n", getrank(Root, x));break;
			case 4: printf("%d\n", getx(Root, x));break;
			case 5: printf("%d\n", prev(Root, x, t));break;
			case 6: printf("%d\n", next(Root, x, t));break;
		}
	}
	
	#if defined DEBUG
	cout << endl << (double)clock()/CLOCKS_PER_SEC << endl;
	#endif
	return 0;
}