7K12 blog

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

NyaaLIB::DS_DynamicList

動的リスト
ユニークな要素を扱うリストで要素の相対位置をO(1)で取得できる
リストという名前を付けたけど、内部で使ってるデータ構造は unorderd_map
注意点: イテレータは存在しないので全要素を出力するときは下記のようにする

DS_DynamicList<long long> dlist(LLONG_MAX);
for (auto x = dlist.begin_val(); x != dlist.end_val(); x = dlist.next_val(x)) std::cout << x << std::endl;
  • 計算量

clear と init はO(N)、それ以外は全てO(1)

  • constructor

DS_DynamicList(inf): 要素数ゼロのリストを生成(infは番兵)
DS_DynamicList(c, inf): コンテナcでリストを生成(infは番兵)

  • list interface

void clear(): 全ての要素を削除
bool push_back(T x): 末尾に要素xを追加
bool push_front(T x): 先頭に要素xを追加
ll size(): 全体サイズを取得

  • original interface

T back(): 末尾要素( end の1つ前)を取得(要素数ゼロならinfを返す)
T begin_val(): 先頭要素を取得(要素数ゼロならinfを返す)
it end_val(): 末尾要素( end の1つ前)を取得(要素数ゼロならinfを返す)
bool find(x): 要素xが存在するかどうか
T front(): 先頭要素を取得(要素数ゼロならinfを返す)
T next_val(x): 要素xの次の要素を取得(存在しない要素のとき引数をそのまま返し、番兵のときinfを返す)
T prev_val(x): 要素xの前の要素を取得(存在しない要素のとき引数をそのまま返し、番兵のときinfを返す)
bool change(x, y): 要素xを要素yに変更(無効な引数のとき何もせずfalseを返す)
bool erase(x): 要素xを削除(無効な引数のとき何もせずfalseを返す)
void init(c): コンテナcで初期化
bool next_insert(x, y): 要素xの次の位置にyを挿入(無効な引数のとき何もせずfalseを返す)
bool prev_insert(x, y): 要素xの前の位置にyを挿入(無効な引数のとき何もせずfalseを返す)
void swap(x, y): 要素xとyをswapする(無効な引数のとき何もせずfalseを返す)

#include <bits/stdc++.h>

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

	template <class T> struct DS_DynamicList
	{
		using ll = long long;
		ll n = 0;
		ll inf = LLONG_MAX;
		std::unordered_map<T, ll> next, prev;
		DS_DynamicList(ll inf) : inf(inf) { clear(); }
		template <class C> DS_DynamicList(C& c, ll inf) : n((ll)c.size()), inf(inf) { init(c); }
		// list interface
		void clear(void) { n = 0, next.clear(), prev.clear(), next[-inf] = inf, prev[-inf] = -inf, next[inf] = inf, prev[inf] = -inf; }
		bool push_back(T x) { return next_insert(back(), x); }
		bool push_front(T x) { return prev_insert(front(), x); }
		ll size(void) { return n; }
		// original interface
		T back(void) { return prev[inf]; }
		T begin_val(void) { return next[-inf]; }
		T end_val(void) { return inf; }
		bool find(T x) { return (next.find(x) != next.end()); }
		T front(void) { return next[-inf]; }
		T next_val(T x) { return (next.find(x) == next.end()) ? x : next[x]; }
		T prev_val(T x) { return (prev.find(x) == prev.end()) ? x : prev[x]; }
		bool change(T x, T y)
		{
			if (!find_val(x) || !find_val(y)) return false;
			prev[y] = prev[x], next[y] = next[x], prev.erase(x), next.erase(x);
			return true;
		}
		bool erase(T x)
		{
			if (!find(x)) return false;
			ll y = prev[x]; ll z = next[x]; n--;
			next[y] = z, prev[z] = y, next.erase(x), prev.erase(x);
			return true;
		}
		template <class C> void init(C& c)
		{
			next.clear(), prev.clear();
			next[-inf] = c[0], prev[-inf] = inf, next[inf] = inf, prev[inf] = c[n - 1];
			next[c[0]] = c[1], prev[c[0]] = -inf, next[c[n - 1]] = inf, prev[c[n - 1]] = c[n - 2];
			for (ll i = 1; i < n - 1; i++) prev[c[i]] = c[i - 1], next[c[i]] = c[i + 1];
			if (next.size() != n - 2) next.clear(), prev.clear(), n = 0;
		}
		bool next_insert(T x, T y)
		{
			if (!(find(x)) || find(y)) return false;
			ll temp = next[x]; n++;
			next[x] = y, prev[y] = x, next[y] = temp, prev[temp] = y;
			return true;
		}
		bool prev_insert(T x, T y)
		{
			if (!(find(x)) || find(y)) return false;
			ll temp = prev[x]; n++;
			prev[x] = y, prev[y] = temp, next[y] = x, next[temp] = y;
			return true;
		}
		bool swap(T x, T y)
		{
			if (!find(x) || !find(y) || abs(x) == inf || abs(y) == inf) return false;
			ll a = prev[x]; ll b = next[x]; ll c = prev[y]; ll d = next[y];
			if (c == x) next[a] = y, next[y] = x, next[x] = d, prev[y] = a, prev[x] = y, prev[d] = x;
			else if (d == x) next[c] = x, next[x] = y, next[y] = b, prev[x] = c, prev[y] = x, prev[b] = y;
			else next[a] = y, next[y] = b, next[c] = x, next[x] = d, prev[y] = a, prev[b] = y, prev[x] = c, prev[d] = x;
			return true;
		}
	};
}

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