Lib/K番目に小さい数

code:cpp

struct GetKth{

multiset<ll> lower;

multiset<ll> upper;

ll k;

GetKth(ll a){

k = a;

}

void insert(ll n){

lower.insert(n);

if((ll)lower.size() > k){

ll a = *lower.rbegin();

lower.erase(lower.find(a));

upper.insert(a);

}

}

ll get(){

if((ll)lower.size() < k) return inf;

else return *lower.rbegin();

}

void erase(ll n){

if(n <= get()){

// print("erase",n);

lower.erase(lower.find(n));

if((ll)upper.size() > 0){

ll a = *upper.begin();

// print("move",a);

upper.erase(upper.find(a));

lower.insert(a);

}

}else{

upper.erase(upper.find(n));

}

}

ll size(){

return upper.size() + lower.size();

}

};

Todo:逆も書く(最悪-1倍すればいいが……)