欲張りマルチセット
priority_queueとかmultisetとか使い分けるのが面倒な人にオススメ（適当）
内部に unordered_map を持つことで count(x) を定数時間に高速化する工夫をしてある
https://rsk0315.hatenablog.com/entry/2019/09/09/214811
namespace LIB { template<class T, class U=less<T>, class F=std::hash<T>>struct AhriSet { using it=typename multiset<T,U>::iterator; multiset<T,U> s; unordered_map<T,ll,F> m; AhriSet() {} AhriSet(vl& v){ forx(e,v) push(e); } it begin(){ return s.begin(); } T back(){ return *s.rbegin(); } vo clear(vo){ s.clear(),m.clear(); } ll count() { return lsz(m); } ll count(T x){ return ll(m.count(x)); } bo empty(vo) { return s.empty(); } it end() { return s.end(); } bo find(T x) { return s.find(x)!=s.end(); } T front() { return *s.begin(); } it lower_bound(T x) { return s.lower_bound(x); } ll lower_bound_val(T x) { return *s.lower_bound(x); } T pop(T x){ if(m.count(x)==0) return inf; s.erase(s.find(x)); if(--m[x]==0) m.erase(x); return x; } T pop_back(){ return pop(*s.rbegin()); } T pop_front() { return pop(*s.begin()); } vo push(T x){ s.insert(x),m[x]++; } vo push_back(T x) { push(x); } vo push_front(T x) { push(x); } ll size() { return ll(s.size()); } it upper_bound(T x) { return s.upper_bound(x); } ll upper_bound_val(T x) { return *s.upper_bound(x); } bo operator==(const AhriSet& as) { return (s==as.s); } }; }
