[abc] AtCoder Beginner Contest 241 D

前言

传送门 :

思路

由于 2 e 5 2e5 2e5的数据量范围在 1 e 18 1e18 1e18之内,考虑对于每次查询使用二分进行优化

但是二分的前提是有序, s o r t sort sort显然会 t t t,如果使用 v e c t o r vector vector其插入时间为 o （ n ） o（n） o（n）

因此需要使用到 m u l t i s e t multiset multiset,它可以在 l o g n logn logn的级别插入一个数,并且保证有序,同

时序列还允许出现重复的数。

当然除此之外还有要注意的是 :

i t = m u l . l o w e r _ b o u n d it = mul.lower\_bound it=mul.lower_bound i t = l o w e r _ b o u n d ( m u l . b e g i n − e n d ) it = lower\_bound(mul.begin -end) it=lower_bound(mul.begin−end)

使用下者也会导致 t l e tle tle,因为下者的时间复杂度是 n 2 l o g n n^2logn n2logn

具体看代码

Mycode

void solve()
{
	multiset mul;
	int n;cin>>n;
	while(n -- ){
		char op[2];cin>>op;
		ll k,x;
		
		if(*op == '1'){
			cin>>x;
			mul.insert(x);
		}else if(*op == '2'){
			cin>>x>>k;
			
			auto it = mul.upper_bound(x);
			while(k && it!=mul.begin()){
				k -- ;
				it -- ;
				
			}
			if(k){
				cout