7K12 blog

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

NyaaLIB::StaticList

静的リスト
ユニークな要素を扱うリストで要素の絶対位置をO(1)で取得できる
リストという名前を付けたけど、内部で使ってるデータ構造は deque と unorderd_map

  • deque interface

T& operator [](ll i): 値[i]を取得 O(1)
T back(): 末尾要素( end の1個前)を取得 O(log N)
it begin(): 先頭を指すイテレータを取得 O(1)
it end(): 末尾を指すイテレータを取得 O(1)
bool find(T x): xが存在するかどうか O(1)
T front(): 先頭要素を取得 O(log N)
ll size(): 全体サイズ O(1)
void push_back(T x): 末尾にxを追加 O(1)
void push_front(T x): 先頭にxを追加 O(N)

  • original interface

void change_val(T x, T y): 値xを値yに変更(重複する値など無効な引数のときは何もしない) O(N)
bool find_val(T x): 値xが存在するか検索 O(1)
ll get_idx(T x): 値指定で絶対位置(インデックス)を取得 O(1)
ll get_val(ll i): インデックス指定で値を取得 O(1)
T next_val(T x): 値xの次の要素を取得 O(1)
T prev_val(T x): 値xの前の要素を取得 O(1)
void sort_val(void): 値をソートする O(N log N)
void swap_idx(ll i1, ll i2): インデックス指定で2要素をswapする O(1)
void swap_val(T x1, T x2): 値指定で2要素をswapする O(1)

namespace NyaaLIB
{

	/**
	* @brief 静的リスト
	* @note
	* ユニークな要素を扱うリスト
	* 要素の絶対位置を取得できる
	**/

	template <class T> struct DS_StaticList
	{
		using ll = long long;
		using it = typename std::deque<T>::iterator;
		ll n = 0;
		std::deque<T> val;
		std::unordered_map<T, ll> idx;
		DS_StaticList() {}
		template <class C> DS_StaticList(C& c) : n((ll)c.size()) { for (ll i = 0; i < n; i++) val.push_back(c[i]), idx[c[i]] = i; }
		// deque interface
		T& operator [](ll i) { return val[i]; }
		T back(void) { return val.back(); }
		it begin(void) { return val.begin(); }
		it end(void) { return val.end(); }
		T front(void) { return val.front(); }
		void push_back(T x) { val.push_back(x); idx[x] = n++; }
		void push_front(T x) { val.push_front(x); n++; for (ll i = 0; i < n; i++) idx[val[i]] = i; }
		ll size(void) { return n; }
		// original interface
		void change_val(T x, T y) { if (find_val(x) && !find_val(y)) val[idx[x]] = y, idx[y] = idx[x], idx.erase(x); }
		bool find_val(T x) { return (idx.find(x) != idx.end()); }
		ll get_idx(T x) { return idx[x]; }
		ll get_val(ll i) { return val[i]; }
		T next_val(T x) { return (idx[x] == n - 1) ? x : val[idx[x] + 1]; }
		T prev_val(T x) { return (idx[x] == 0) ? x : val[idx[x] - 1]; }
		void sort_val(void) { std::sort(val.begin(), val.end()); for (ll i = 0; i < n; i++) idx[val[i]] = i; }
		void swap_idx(ll i1, ll i2) { if (0 <= i1 && i1 < n && 0 <= i2 && i2 < n) std::swap(val[i1], val[i2]), std::swap(idx[val[i1]], idx[val[i2]]); }
		void swap_val(T x1, T x2) { if (find_val(x1) && find_val(x2)) std::swap(val[idx[x1]], val[idx[x2]]), std::swap(idx[x1], idx[x2]); }
	};
}

実装例
https://atcoder.jp/contests/abc250/submissions/31580811