欲張りマルチセット
multiset に標準コンテナの頻出関数を全部実装した欲張りデータ構造
色々なコンテナを使い分けて処理する操作毎に関数名を使い分けるのが面倒な人にオススメ（適当）
内部に unordered_map を持つことで count(x) を定数時間に高速化する工夫をしてある
https://rsk0315.hatenablog.com/entry/2019/09/09/214811
- multiset interface
it begin(): 先頭を指すイテレータを取得 O(1)
void clear(void): クリア O(N)
ll count(T x): xの個数 O(1)
bool empty(void): 空かどうか O(1)
it end(): 末尾を指すイテレータを取得 O(1)
ll erase(T x): xを全部削除 O(log N)
bool find(T x): xが存在するかどうか O(1)
void insert(T x): xを追加 O(log N)
it lower_bound(T x): 二分探索 O(log N)
ll size(): 全体サイズ O(1)
it upper_bound(T x): 二分探索 O(log N)
bool operator == (const AhriSet& as): 同値集合判定 O(N) サイズが異るときは O(1)
- deque interface
T back(): 末尾要素（ end の1個前）を取得 O(log N)
T front(): 先頭要素を取得 O(log N)
void push_back(T x): xを追加（ただし内部でソートされる）O(log N)
void push_front(T x): xを追加（ただし内部でソートされる）O(log N)
T pop_back(): 末尾要素を削除して取得 O(log N)
T pop_front(): 先頭要素を削除して取得 O(log N)
- priority queue interface
void push(T x): xを追加 O(log N)
T top(): 先頭要素を取得 O(log N)
T pop(): 先頭要素を削除して取得 O(log N)
- original interface
ll lower_bound_val(T x): xを二分探索してll型で返す O(log N)
ll unique_size(): ユニークな要素数 O(1)
ll upper_bound_val(T x): xを二分探索してll型で返す O(log N)
ll erase1(T x): xを1個削除 O(log N)
#include <bits/stdc++.h> namespace LIB { /** * @brief 欲張りマルチセット * @note * 内部にunorderd_mapを持つことでcount(x)を定数時間に高速化 * 標準コンテナの頻出関数を全部定義したマルチセット **/ template <class T = long long, class U = std::less<T>, class F = std::hash<T>> struct AhriSet { // 降順は AhriSet<T, greater<T>> （デフォルトは昇順） using ll = long long; using it = typename std::multiset<T, U>::iterator; std::multiset<T, U> s; std::unordered_map<T, ll, F> m; DS_AhriSet() {} DS_AhriSet(std::vector<ll>& v) { for (auto e : v) push(e); } // multiset interface it begin() { return s.begin(); } void clear(void) { s.clear(), m.clear(); } ll count(T x) { return m[x]; } bool empty(void) { return s.empty(); } it end() { return s.end(); } ll erase(T x) { m.erase(); return s.erase(x); } bool find(T x) { return s.find(x); } void insert(T x) { m[x]++, s.insert(x); } it lower_bound(T x) { return s.lower_bound(x); } ll size() { return ll(s.size()); } it upper_bound(T x) { return s.upper_bound(x); } bool operator == (const AhriSet& as) { return (s == as.s); } // deque interface T back() { return *s.rbegin(); } T front() { return *s.begin(); } void push_back(T x) { m[x]++, s.insert(x); } void push_front(T x) { m[x]++, s.insert(x); } T pop_back() { auto res = *s.rbegin(); if (--m[res] == 0) m.erase(res); s.erase(s.find(res)); return res; } T pop_front() { auto res = *s.begin(); if (--m[res] == 0) m.erase(res); s.erase(s.find(res)); return res; } // priority queue interface void push(T x) { m[x]++, s.insert(x); } T top(void) { return *s.begin(); } T pop(void) { T res = *s.begin(); if (--m[res] == 0) m.erase(res); s.erase(s.find(res)); return res; } // original interface ll lower_bound_val(T x) { return *s.lower_bound(x); } ll unique_count(const T& x) { return ll(find(x)); } ll unique_size() { return ll(m.size()); } ll upper_bound_val(T x) { return *s.upper_bound(x); } ll erase1(T x) { if (m.count(x) == 0) return 0; if (m[x] == 1) s.erase(x), m.erase(x); else s.erase(s.find(x)), m[x]--; return 1; } }; }