记录编号	149421	评测结果	AAAAAAAAAA
题目名称	[Tyvj 1728]普通平衡树	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.327 s
提交时间	2015-02-24 10:18:21	内存使用	0.31 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<map>
#include<ext/pb_ds/assoc_container.hpp>
using namespace std;
using namespace __gnu_pbds;
typedef long long LL;
tree<LL,null_mapped_type,less<LL>,rb_tree_tag,tree_order_statistics_node_update> T;
//tree<LL,null_type,less<LL>,rb_tree_tag,tree_order_statistics_node_update> T;
map<int,int> MP;
int main(){
	freopen("phs.in","r",stdin);
	freopen("phs.out","w",stdout);
	int Q;
	scanf("%d",&Q);
	int opt;
	LL x;
	for(int i=1;i<=Q;i++){
		scanf("%d%lld",&opt,&x);
		if(opt==1) T.insert((x<<20)+(MP[x]++));
		else if(opt==2){
			T.erase(T.find((x<<20)+(--MP[x])));
			if(!MP[x]) MP.erase(MP.find(x));
		}
		else if(opt==3)	printf("%d\n",T.order_of_key(x<<20)+1);
		else if(opt==4) printf("%lld\n",*T.find_by_order(x-1)>>20);
		else if(opt==5){
			map<int,int>::iterator key=MP.lower_bound(x);key--;
			printf("%d\n",key->first);
		}
		else if(opt==6){
			map<int,int>::iterator key=MP.upper_bound(x);
			printf("%d\n",key->first);
		}
	}
	return 0;
}