sotanishy's code snippets for competitive programming
View the Project on GitHub sotanishy/cp-library-cpp
#include "data-structure/persistent_queue.hpp"
永続キューは,過去のバージョンを保持するキューである.この実装では内部で永続配列を用いている.
空間計算量: $O(m \log n)$, $m$ は変更の数
int size()
bool empty()
T front()
T back()
PersistentQueue push(T val)
val
PersistentQueue pop()
#pragma once #include <cassert> #include "persistent_array.hpp" template <typename T> class PersistentQueue { public: PersistentQueue() : first(0), last(0) {} int size() const { return last - first; } bool empty() const { return size() == 0; } T front() const { assert(!empty()); return pa.get(first); } T back() const { assert(!empty()); return pa.get(last - 1); } PersistentQueue push(const T& val) const { return PersistentQueue(pa.set(last, val), first, last + 1); } PersistentQueue pop() const { assert(!empty()); return PersistentQueue(pa, first + 1, last); } private: PersistentArray<T> pa; int first, last; PersistentQueue(const PersistentArray<T>& pa, int first, int last) : pa(pa), first(first), last(last) {} };
#line 2 "data-structure/persistent_queue.hpp" #include <cassert> #line 2 "data-structure/persistent_array.hpp" #include <memory> #include <vector> template <typename T, int B = 2> class PersistentArray { public: PersistentArray() = default; explicit PersistentArray(const std::vector<T>& v) { for (int i = 0; i < (int)v.size(); ++i) root = set(root, i, v[i]); } T get(int k) const { return get(root, k); } PersistentArray set(int k, const T& x) const { return PersistentArray(set(root, k, x)); } private: struct Node; using node_ptr = std::shared_ptr<Node>; struct Node { T val; node_ptr ch[B]; }; node_ptr root = nullptr; explicit PersistentArray(const node_ptr& root) : root(root) {} T get(const node_ptr& t, int k) const { if (k == 0) return t->val; return get(t->ch[k % B], k / B); } node_ptr set(const node_ptr& t, int k, const T& x) const { node_ptr res = t ? std::make_shared<Node>(*t) : std::make_shared<Node>(); if (k == 0) { res->val = x; } else { res->ch[k % B] = set(res->ch[k % B], k / B, x); } return res; } }; #line 5 "data-structure/persistent_queue.hpp" template <typename T> class PersistentQueue { public: PersistentQueue() : first(0), last(0) {} int size() const { return last - first; } bool empty() const { return size() == 0; } T front() const { assert(!empty()); return pa.get(first); } T back() const { assert(!empty()); return pa.get(last - 1); } PersistentQueue push(const T& val) const { return PersistentQueue(pa.set(last, val), first, last + 1); } PersistentQueue pop() const { assert(!empty()); return PersistentQueue(pa, first + 1, last); } private: PersistentArray<T> pa; int first, last; PersistentQueue(const PersistentArray<T>& pa, int first, int last) : pa(pa), first(first), last(last) {} };