静的リスト
ユニークな要素を扱うリストで要素の絶対位置を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]); } }; }
