7K12 blog

猫でも分かるアルゴリズム解説

NyaaLIB::DS_AhriSet

欲張りマルチセット
https://www.google.com/search?q=gwen+lol&source=lnms&tbm=isch
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 DS_NyaaGwenSet& gs): 同値集合判定 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 NyaaLIB
{
	/**
	* @brief 欲張りマルチセット
	* @note
	* 内部にunorderd_mapを持つことでcount(x)を定数時間に高速化
	* 標準コンテナの頻出関数を全部定義したマルチセット
	**/

	template <class T = long long, class U = std::less<T>, class F = std::hash<T>> struct DS_AhriSet
	{	// 降順は DS_NyaaPQMset<ll, greater<ll>> (デフォルトは昇順)
		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.count(x) == 0) ? 0 : 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 DS_GwenSet& gs) { return (s == gs.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_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;
		}
	};
}

実装例
https://atcoder.jp/contests/arc006/submissions/33412441