记录编号	489134	评测结果	AAAAAAAAAA
题目名称	[Tyvj 1728]普通平衡树	最终得分	100
用户昵称	Lazer2001	是否通过	通过
代码语言	C++	运行时间	0.628 s
提交时间	2018-02-27 16:11:08	内存使用	0.19 MiB

# include <bits/stdc++.h>
# include <ext/pb_ds/tree_policy.hpp>
# include <ext/pb_ds/hash_policy.hpp>
# include <ext/pb_ds/assoc_container.hpp>

using namespace std ;
using namespace __gnu_pbds ;

gp_hash_table < int, int > H ;
__gnu_pbds :: tree < pair < int, int >, null_mapped_type, less < pair < int, int > >, rb_tree_tag, tree_order_statistics_node_update > T ;
//__gnu_pbds :: tree < pair < int, int >, null_type, less < pair < int, int > >, rb_tree_tag, tree_order_statistics_node_update > T ;

int main ( )  {
	freopen ( "phs.in", "r", stdin ) ;
	freopen ( "phs.out", "w", stdout ) ;
	
	int n ;
	scanf ( "%d", & n ) ;
	while ( n -- )  {
		static int opt, x ;
		scanf ( "%d%d", & opt, & x ) ;
		switch ( opt )  {
			case 1 :  {
				T.insert ( make_pair ( x, ++ H [x] ) ) ;
				break ;
			}
			case 2 :  {
				T.erase ( make_pair ( x, H [x] --) ) ;
				break ;
			}
			case 3 :  {
				printf ( "%d\n", ( int ) T.order_of_key ( make_pair ( x, 0 ) ) + 1 ) ;
				break ;
			}
			case 4 :  {
				printf ( "%d\n", T.find_by_order ( x - 1 ) -> first ) ;
				break ;
			}
			case 5 :  {
				printf ( "%d\n", T.find_by_order ( T.order_of_key ( make_pair ( x, 0 ) ) - 1 ) -> first ) ;
				break ;
			}
			case 6 :  {
				printf ( "%d\n", T.upper_bound ( make_pair ( x, INT_MAX ) ) -> first ) ;
				break ;
			}
		}
	}
}