This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub suisen-cp/cp-library-cpp
#define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A" #include <iostream> #include <limits> #include "library/datastructure/segment_tree/persistent_lazy_segment_tree.hpp" template <typename T, T(*op)(T, T), T(*e)(), typename F, T(*mapping)(F, T)> struct NaiveSolutionForLazySegmentTree { NaiveSolutionForLazySegmentTree() = default; NaiveSolutionForLazySegmentTree(const std::vector<T> &dat) : _n(dat.size()), _dat(dat) {} T get(int i) const { assert(0 <= i and i < _n); return _dat[i]; } void set(int i, const T& val) { assert(0 <= i and i < _n); _dat[i] = val; } T prod_all() const { return prod(0, _n); } T prod(int l, int r) const { assert(0 <= l and l <= r and r <= _n); T res = e(); for (int i = l; i < r; ++i) res = op(res, _dat[i]); return res; } void apply_all(const F &f) { apply(0, _n, f); } void apply(int l, int r, const F &f) { assert(0 <= l and l <= r and r <= _n); for (int i = l; i < r; ++i) _dat[i] = mapping(f, _dat[i]); } template <typename Pred> int max_right(int l, Pred &&pred) const { assert(0 <= l and l <= _n); T sum = e(); for (int r = l; r < _n; ++r) { T next_sum = op(sum, _dat[r]); if (not pred(next_sum)) return r; sum = std::move(next_sum); } return _n; } template <typename Pred> int min_left(int r, Pred &&pred) const { assert(0 <= r and r <= _n); T sum = e(); for (int l = r; l > 0; --l) { T next_sum = op(_dat[l - 1], sum); if (not pred(next_sum)) return l; sum = std::move(next_sum); } return 0; } private: int _n; std::vector<T> _dat; }; /** * Range Update Range Sum */ struct S { long long sum; int len; S() = default; S(long long sum, int len) : sum(sum), len(len) {} bool operator==(const S &other) const { return sum == other.sum and len == other.len; } bool operator!=(const S &other) const { return not operator==(other); } }; struct F { static constexpr int identity = std::numeric_limits<int>::max(); int val; F() : val(identity) {} F(int val) : val(val) {} }; S op(S x, S y) { return S{ x.sum + y.sum, x.len + y.len }; } S e() { return S{ 0LL, 0 }; } S mapping(F f, S x) { return f.val == F::identity ? x : S{ (long long) f.val * x.len, x.len }; } F composition(F f, F g) { return f.val == F::identity ? g : f; } F id() { return F{}; } using Tree = suisen::PersistentLazySegmentTree<S, op, e, F, mapping, composition, id>; using Naive = NaiveSolutionForLazySegmentTree<S, op, e, F, mapping>; #include <random> #include <algorithm> constexpr int Q_get = 0; constexpr int Q_set = 1; constexpr int Q_prod = 2; constexpr int Q_prod_all = 3; constexpr int Q_apply = 4; constexpr int Q_apply_all = 5; constexpr int Q_max_right = 6; constexpr int Q_min_left = 7; constexpr int QueryTypeNum = 8; void test() { constexpr int N = 3000, Q = 3000, MAX_VAL = 1000000000; std::mt19937 rng{std::random_device{}()}; Tree::init_pool(1000000); std::vector<S> init(N); for (int i = 0; i < N; ++i) init[i] = { (long long) rng() % MAX_VAL, 1 }; std::vector<Tree> ts; std::vector<Naive> naive_sols; ts.push_back(Tree{init}); naive_sols.push_back(Naive{init}); for (int i = 0; i < Q; ++i) { const int query_type = rng() % QueryTypeNum; const int sequence_id = rng() % ts.size(); auto &act = ts[sequence_id]; auto &exp = naive_sols[sequence_id]; if (query_type == Q_get) { const int i = rng() % N; assert(act.get(i) == exp.get(i)); } else if (query_type == Q_set) { const int i = rng() % N; const S v = { (long long) rng() % MAX_VAL, 1 }; ts.push_back(act.set(i, v)); naive_sols.push_back(exp); naive_sols.back().set(i, v); } else if (query_type == Q_prod) { const int l = rng() % (N + 1); const int r = l + rng() % (N - l + 1); assert(act.prod(l, r) == exp.prod(l, r)); } else if (query_type == Q_prod_all) { assert(act.prod_all() == exp.prod_all()); } else if (query_type == Q_apply) { const int l = rng() % (N + 1); const int r = l + rng() % (N - l + 1); const int f = rng() % MAX_VAL; ts.push_back(act.apply(l, r, f)); naive_sols.push_back(exp); naive_sols.back().apply(l, r, f); } else if (query_type == Q_apply_all) { const int f = rng() % MAX_VAL; ts.push_back(act.apply_all(f)); naive_sols.push_back(exp); naive_sols.back().apply_all(f); } else if (query_type == Q_max_right) { const int l = rng() % (N + 1); const int r = l + rng() % (N - l + 1); long long sum = std::max(0LL, exp.prod(l, r).sum + int(rng() % MAX_VAL) - MAX_VAL / 2); auto pred = [&](const S &x) { return x.sum <= sum; }; assert(act.max_right(l, pred) == exp.max_right(l, pred)); } else if (query_type == Q_min_left) { const int l = rng() % (N + 1); const int r = l + rng() % (N - l + 1); long long sum = std::max(0LL, exp.prod(l, r).sum + int(rng() % MAX_VAL) - MAX_VAL / 2); auto pred = [&](const S &x) { return x.sum <= sum; }; assert(act.min_left(r, pred) == exp.min_left(r, pred)); } else { assert(false); } } } int main() { test(); std::cout << "Hello World" << std::endl; return 0; }
#line 1 "test/src/datastructure/segment_tree/persistent_lazy_segment_tree/dummy.test.cpp" #define PROBLEM "https://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=ITP1_1_A" #include <iostream> #include <limits> #line 1 "library/datastructure/segment_tree/persistent_lazy_segment_tree.hpp" #include <cassert> #line 1 "library/util/object_pool.hpp" #include <deque> #include <vector> namespace suisen { template <typename T, bool auto_extend = false> struct ObjectPool { using value_type = T; using value_pointer_type = T*; template <typename U> using container_type = std::conditional_t<auto_extend, std::deque<U>, std::vector<U>>; container_type<value_type> pool; container_type<value_pointer_type> stock; decltype(stock.begin()) it; ObjectPool() : ObjectPool(0) {} ObjectPool(int siz) : pool(siz), stock(siz) { clear(); } int capacity() const { return pool.size(); } int size() const { return it - stock.begin(); } value_pointer_type alloc() { if constexpr (auto_extend) ensure(); return *it++; } void free(value_pointer_type t) { *--it = t; } void clear() { int siz = pool.size(); it = stock.begin(); for (int i = 0; i < siz; i++) stock[i] = &pool[i]; } void ensure() { if (it != stock.end()) return; int siz = stock.size(); for (int i = siz; i <= siz * 2; ++i) { stock.push_back(&pool.emplace_back()); } it = stock.begin() + siz; } }; } // namespace suisen #line 7 "library/datastructure/segment_tree/persistent_lazy_segment_tree.hpp" namespace suisen { template <typename T, T(*op)(T, T), T(*e)(), typename F, T(*mapping)(F, T), F(*composition)(F, F), F(*id)()> struct PersistentLazySegmentTree { struct Node; using value_type = T; using operator_type = F; using node_type = Node; using node_pointer_type = node_type*; struct Node { static inline ObjectPool<node_type> _pool; node_pointer_type _ch[2]{ nullptr, nullptr }; value_type _dat; operator_type _laz; Node() : _dat(e()), _laz(id()) {} static node_pointer_type clone(node_pointer_type node) { return &(*_pool.alloc() = *node); } static void update(node_pointer_type node) { node->_dat = op(node->_ch[0]->_dat, node->_ch[1]->_dat); } template <bool do_clone = true> static auto push(node_pointer_type node) { node_pointer_type res = node; if constexpr (do_clone) res = clone(res); res->_ch[0] = apply_all(res->_ch[0], res->_laz); res->_ch[1] = apply_all(res->_ch[1], res->_laz); res->_laz = id(); if constexpr (do_clone) { return res; } else { return; } } static bool is_leaf(node_pointer_type node) { return not node->_ch[0]; } static node_pointer_type build(const std::vector<value_type>& dat) { auto rec = [&](auto rec, int l, int r) -> node_pointer_type { node_pointer_type res = _pool.alloc(); if (r - l == 1) { res->_dat = dat[l]; res->_laz = id(); } else { int m = (l + r) >> 1; res->_ch[0] = rec(rec, l, m), res->_ch[1] = rec(rec, m, r); update(res); res->_laz = id(); } return res; }; return rec(rec, 0, dat.size()); } static value_type prod_all(node_pointer_type node) { return node ? node->_dat : e(); } static value_type prod(node_pointer_type node, int tl, int tr, int ql, int qr, const operator_type &f = id()) { if (tr <= ql or qr <= tl) return e(); if (ql <= tl and tr <= qr) return mapping(f, node->_dat); int tm = (tl + tr) >> 1; operator_type g = composition(f, node->_laz); return op(prod(node->_ch[0], tl, tm, ql, qr, g), prod(node->_ch[1], tm, tr, ql, qr, g)); } static node_pointer_type apply_all(node_pointer_type node, const operator_type &f) { if (not node) return nullptr; node_pointer_type res = clone(node); res->_dat = mapping(f, res->_dat); res->_laz = composition(f, res->_laz); return res; } static node_pointer_type apply(node_pointer_type node, int tl, int tr, int ql, int qr, const operator_type &f) { if (tr <= ql or qr <= tl) return node; if (ql <= tl and tr <= qr) return apply_all(node, f); node_pointer_type res = push(node); int tm = (tl + tr) >> 1; res->_ch[0] = apply(res->_ch[0], tl, tm, ql, qr, f); res->_ch[1] = apply(res->_ch[1], tm, tr, ql, qr, f); update(res); return res; } template <typename Func> static auto update_leaf(node_pointer_type node, int siz, int i, Func &&f) { static std::vector<node_pointer_type> path; node_pointer_type res = clone(node); node_pointer_type cur = res; for (int l = 0, r = siz; r - l > 1;) { path.push_back(cur); push</*do_clone = */false>(cur); int m = (l + r) >> 1; if (i < m) { cur = cur->_ch[0]; r = m; } else { cur = cur->_ch[1]; l = m; } } cur->_dat = f(cur->_dat); while (path.size()) update(path.back()), path.pop_back(); return res; } static value_type get(node_pointer_type node, int siz, int i) { operator_type f = id(); node_pointer_type cur = node; for (int l = 0, r = siz; r - l > 1;) { f = composition(f, cur->_laz); int m = (l + r) >> 1; if (i < m) { cur = cur->_ch[0]; r = m; } else { cur = cur->_ch[1]; l = m; } } return mapping(f, cur->_dat); } template <typename Func> static node_pointer_type apply(node_pointer_type node, int siz, int i, Func&& f) { return update_leaf(node, siz, i, [&](const value_type &v) { return f(v); }); } static node_pointer_type set(node_pointer_type node, int siz, int i, const value_type& dat) { return apply(node, siz, i, [&](const value_type&) { return dat; }); } template <typename Pred> static int max_right(node_pointer_type node, int siz, int l, Pred&& pred) { assert(pred(e())); auto rec = [&](auto rec, node_pointer_type cur, int tl, int tr, value_type& sum, const operator_type &f) -> int { if (tr <= l) return tr; if (l <= tl) { value_type nxt_sum = op(sum, mapping(f, cur->_dat)); if (pred(nxt_sum)) { sum = std::move(nxt_sum); return tr; } if (tr - tl == 1) return tl; } int tm = (tl + tr) >> 1; operator_type g = composition(f, cur->_laz); int res_l = rec(rec, cur->_ch[0], tl, tm, sum, g); return res_l != tm ? res_l : rec(rec, cur->_ch[1], tm, tr, sum, g); }; value_type sum = e(); return rec(rec, node, 0, siz, sum, id()); } template <typename Pred> static int min_left(node_pointer_type node, int siz, int r, Pred&& pred) { assert(pred(e())); auto rec = [&](auto rec, node_pointer_type cur, int tl, int tr, value_type& sum, const operator_type &f) -> int { if (r <= tl) return tl; if (tr <= r) { value_type nxt_sum = op(mapping(f, cur->_dat), sum); if (pred(nxt_sum)) { sum = std::move(nxt_sum); return tl; } if (tr - tl == 1) return tr; } int tm = (tl + tr) >> 1; operator_type g = composition(f, cur->_laz); int res_r = rec(rec, cur->_ch[1], tm, tr, sum, g); return res_r != tm ? res_r : rec(rec, cur->_ch[0], tl, tm, sum, g); }; value_type sum = e(); return rec(rec, node, 0, siz, sum, id()); } template <typename OutputIterator> static void dump(node_pointer_type node, OutputIterator it) { if (not node) return; auto rec = [&](auto rec, node_pointer_type cur, const operator_type &f) -> void { if (is_leaf(cur)) { *it++ = mapping(f, cur->_dat); } else { *it++ = mapping(f, cur->_dat); rec(rec, cur->_ch[0], composition(cur->_laz, f)), rec(rec, cur->_ch[1], composition(cur->_laz, f)); } }; rec(rec, node, id()); } static std::vector<value_type> dump(node_pointer_type node) { std::vector<value_type> res; dump(node, std::back_inserter(res)); return res; } }; PersistentLazySegmentTree() : _n(0), _root(nullptr) {} explicit PersistentLazySegmentTree(int n) : PersistentLazySegmentTree(std::vector<value_type>(n, e())) {} PersistentLazySegmentTree(const std::vector<value_type>& dat) : _n(dat.size()), _root(node_type::build(dat)) {} static void init_pool(int siz) { node_type::_pool = ObjectPool<node_type>(siz); } static void clear_pool() { node_type::_pool.clear(); } value_type prod_all() { return node_type::prod_all(_root); } value_type prod(int l, int r) { assert(0 <= l and l <= r and r <= _n); return node_type::prod(_root, 0, _n, l, r); } value_type operator()(int l, int r) { return prod(l, r); } PersistentLazySegmentTree apply_all(const operator_type &f) { return PersistentLazySegmentTree(_n, node_type::apply_all(_root, f)); } PersistentLazySegmentTree apply(int l, int r, const operator_type &f) { return PersistentLazySegmentTree(_n, node_type::apply(_root, 0, _n, l, r, f)); } value_type get(int i) { assert(0 <= i and i < _n); return node_type::get(_root, _n, i); } value_type operator[](int i) { return get(i); } template <typename Func> PersistentLazySegmentTree apply(int i, Func&& f) { assert(0 <= i and i < _n); return PersistentLazySegmentTree(_n, node_type::apply(_root, _n, i, std::forward<F>(f))); } PersistentLazySegmentTree set(int i, const value_type& v) { assert(0 <= i and i < _n); return PersistentLazySegmentTree(_n, node_type::set(_root, _n, i, v)); } template <typename Pred> int max_right(int l, Pred&& pred) { assert(0 <= l and l <= _n); return node_type::max_right(_root, _n, l, std::forward<Pred>(pred)); } template <bool(*pred)(value_type)> static int max_right(int l) { return max_right(l, pred); } template <typename Pred> int min_left(int r, Pred&& pred) { assert(0 <= r and r <= _n); return node_type::min_left(_root, _n, r, std::forward<Pred>(pred)); } template <bool(*pred)(value_type)> static int min_left(int r) { return min_left(r, pred); } template <typename OutputIterator> void dump(OutputIterator it) { node_type::dump(_root, it); } std::vector<value_type> dump() { return node_type::dump(_root); } private: int _n; node_pointer_type _root; PersistentLazySegmentTree(int n, node_pointer_type root) : _n(n), _root(root) {} }; } #line 7 "test/src/datastructure/segment_tree/persistent_lazy_segment_tree/dummy.test.cpp" template <typename T, T(*op)(T, T), T(*e)(), typename F, T(*mapping)(F, T)> struct NaiveSolutionForLazySegmentTree { NaiveSolutionForLazySegmentTree() = default; NaiveSolutionForLazySegmentTree(const std::vector<T> &dat) : _n(dat.size()), _dat(dat) {} T get(int i) const { assert(0 <= i and i < _n); return _dat[i]; } void set(int i, const T& val) { assert(0 <= i and i < _n); _dat[i] = val; } T prod_all() const { return prod(0, _n); } T prod(int l, int r) const { assert(0 <= l and l <= r and r <= _n); T res = e(); for (int i = l; i < r; ++i) res = op(res, _dat[i]); return res; } void apply_all(const F &f) { apply(0, _n, f); } void apply(int l, int r, const F &f) { assert(0 <= l and l <= r and r <= _n); for (int i = l; i < r; ++i) _dat[i] = mapping(f, _dat[i]); } template <typename Pred> int max_right(int l, Pred &&pred) const { assert(0 <= l and l <= _n); T sum = e(); for (int r = l; r < _n; ++r) { T next_sum = op(sum, _dat[r]); if (not pred(next_sum)) return r; sum = std::move(next_sum); } return _n; } template <typename Pred> int min_left(int r, Pred &&pred) const { assert(0 <= r and r <= _n); T sum = e(); for (int l = r; l > 0; --l) { T next_sum = op(_dat[l - 1], sum); if (not pred(next_sum)) return l; sum = std::move(next_sum); } return 0; } private: int _n; std::vector<T> _dat; }; /** * Range Update Range Sum */ struct S { long long sum; int len; S() = default; S(long long sum, int len) : sum(sum), len(len) {} bool operator==(const S &other) const { return sum == other.sum and len == other.len; } bool operator!=(const S &other) const { return not operator==(other); } }; struct F { static constexpr int identity = std::numeric_limits<int>::max(); int val; F() : val(identity) {} F(int val) : val(val) {} }; S op(S x, S y) { return S{ x.sum + y.sum, x.len + y.len }; } S e() { return S{ 0LL, 0 }; } S mapping(F f, S x) { return f.val == F::identity ? x : S{ (long long) f.val * x.len, x.len }; } F composition(F f, F g) { return f.val == F::identity ? g : f; } F id() { return F{}; } using Tree = suisen::PersistentLazySegmentTree<S, op, e, F, mapping, composition, id>; using Naive = NaiveSolutionForLazySegmentTree<S, op, e, F, mapping>; #include <random> #include <algorithm> constexpr int Q_get = 0; constexpr int Q_set = 1; constexpr int Q_prod = 2; constexpr int Q_prod_all = 3; constexpr int Q_apply = 4; constexpr int Q_apply_all = 5; constexpr int Q_max_right = 6; constexpr int Q_min_left = 7; constexpr int QueryTypeNum = 8; void test() { constexpr int N = 3000, Q = 3000, MAX_VAL = 1000000000; std::mt19937 rng{std::random_device{}()}; Tree::init_pool(1000000); std::vector<S> init(N); for (int i = 0; i < N; ++i) init[i] = { (long long) rng() % MAX_VAL, 1 }; std::vector<Tree> ts; std::vector<Naive> naive_sols; ts.push_back(Tree{init}); naive_sols.push_back(Naive{init}); for (int i = 0; i < Q; ++i) { const int query_type = rng() % QueryTypeNum; const int sequence_id = rng() % ts.size(); auto &act = ts[sequence_id]; auto &exp = naive_sols[sequence_id]; if (query_type == Q_get) { const int i = rng() % N; assert(act.get(i) == exp.get(i)); } else if (query_type == Q_set) { const int i = rng() % N; const S v = { (long long) rng() % MAX_VAL, 1 }; ts.push_back(act.set(i, v)); naive_sols.push_back(exp); naive_sols.back().set(i, v); } else if (query_type == Q_prod) { const int l = rng() % (N + 1); const int r = l + rng() % (N - l + 1); assert(act.prod(l, r) == exp.prod(l, r)); } else if (query_type == Q_prod_all) { assert(act.prod_all() == exp.prod_all()); } else if (query_type == Q_apply) { const int l = rng() % (N + 1); const int r = l + rng() % (N - l + 1); const int f = rng() % MAX_VAL; ts.push_back(act.apply(l, r, f)); naive_sols.push_back(exp); naive_sols.back().apply(l, r, f); } else if (query_type == Q_apply_all) { const int f = rng() % MAX_VAL; ts.push_back(act.apply_all(f)); naive_sols.push_back(exp); naive_sols.back().apply_all(f); } else if (query_type == Q_max_right) { const int l = rng() % (N + 1); const int r = l + rng() % (N - l + 1); long long sum = std::max(0LL, exp.prod(l, r).sum + int(rng() % MAX_VAL) - MAX_VAL / 2); auto pred = [&](const S &x) { return x.sum <= sum; }; assert(act.max_right(l, pred) == exp.max_right(l, pred)); } else if (query_type == Q_min_left) { const int l = rng() % (N + 1); const int r = l + rng() % (N - l + 1); long long sum = std::max(0LL, exp.prod(l, r).sum + int(rng() % MAX_VAL) - MAX_VAL / 2); auto pred = [&](const S &x) { return x.sum <= sum; }; assert(act.min_left(r, pred) == exp.min_left(r, pred)); } else { assert(false); } } } int main() { test(); std::cout << "Hello World" << std::endl; return 0; }