记录编号	156069	评测结果	AAAAAAAAAA
题目名称	[Tyvj 1728]普通平衡树	最终得分	100
用户昵称	ztx	是否通过	通过
代码语言	C++	运行时间	1.098 s
提交时间	2015-04-01 21:11:46	内存使用	0.31 MiB

/****************************************\
* Author : ztx
* Title  : [bzoj] 3224: Tyvj 1728 普通平衡树
* ALG    : 常用思想 二分
* CMT    :
* Time   :
\****************************************/

#include <cstdio>

int CH , NEG ;
inline void read(int& ret) {
    ret = NEG = 0 ; while (CH=getchar() , CH<'!') ;
    if (CH == '-') NEG = true , CH = getchar() ;
    while (ret = ret*10+CH-'0' , CH=getchar() , CH>'!') ;
    if (NEG) ret = -ret ;
}

#include <deque>

using namespace std ;

deque<int> q ;

int L , R , M ;
inline int Bsearch(int x) {
	L = 0 , R = q.size()-1 ;
	while (L <= R) {
		M = L+(R-L)/2 ;
		if (q[M] >= x) R = M-1 ;
		else L = M+1 ;
	}
	return L ;
}

int n , i , k , cmd , x ;
int main() {
	#define READ
	#ifdef  READ
		freopen("phs.in" ,"r",stdin ) ;
		freopen("phs.out","w",stdout) ;
	#endif
	scanf("%d", &n) ;
	for (i = 0 ; i < n ; i ++ ) {
		read(cmd) , read(x) ;
		if (cmd == 1) { k = Bsearch(x) ; q.insert(q.begin()+k , x) ; }
		if (cmd == 2) { k = Bsearch(x) ; q.erase(q.begin()+k) ; }
		if (cmd == 3) { k = Bsearch(x) ; printf("%d\n", k+1) ; }
		if (cmd == 4) { printf("%d\n", q[x-1]) ; }
		if (cmd == 5) { k = Bsearch(x-1) ; if (q[k]!=x-1) k -- ; printf("%d\n", q[k]) ; }
		if (cmd == 6) { k = Bsearch(x+1) ; printf("%d\n", q[k]) ; }
	}
	#ifdef  READ
		fclose(stdin) ; fclose(stdout) ;
	#else
		getchar() ; getchar() ;
	#endif
	return 0 ;
}