This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub tkmst201/Library
#define PROBLEM "https://judge.yosupo.jp/problem/point_set_range_composite" #include "DataStructure/DynamicSegmentTree.hpp" #include "Mathematics/ModInt.hpp" #include <cstdio> int main() { int N, Q; scanf("%d %d", &N, &Q); using mint = ModInt<998244353>; using pmm = std::pair<mint, mint>; DynamicSegmentTree<pmm> seg(N, pmm(1, 0), [](const pmm & a, const pmm & b) -> pmm { return {a.first * b.first, b.first * a.second + b.second}; }); for (int i = 0; i < N; ++i) { int a, b; scanf("%d %d", &a, &b); seg.set(i, {a, b}); } while (Q--) { int q, a, b, c; scanf("%d %d %d %d", &q, &a, &b, &c); if (q == 0) { seg.set(a, {b, c}); } else { pmm v = seg.fold(a, b); mint ans = v.first * c + v.second; printf("%d\n", ans.val()); } } }
#line 1 "Test/DynamicSegmentTree.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/point_set_range_composite" #line 1 "DataStructure/DynamicSegmentTree.hpp" #include <functional> #include <cassert> #include <stack> #include <cstdint> /** * @brief https://tkmst201.github.io/Library/DataStructure/DynamicSegmentTree.hpp */ template<typename T> struct DynamicSegmentTree { using value_type = T; using const_reference = const value_type &; using size_type = std::size_t; using F = std::function<value_type (const_reference, const_reference)>; private: struct Node; using node_ptr = Node *; using const_ptr = const Node * const; struct Node { value_type val; node_ptr child[2] {nullptr, nullptr}; Node() = default; Node(const_reference val) : val(val) {} }; template<typename U> struct Data { U node; size_type l, r; Data(U node, size_type l, size_type r) : node(node), l(l), r(r) {} }; private: size_type n, n_; int log_n; value_type id_elem; F f; node_ptr root = nullptr; public: DynamicSegmentTree(size_type n, const_reference id_elem, const F & f) : n(n), id_elem(id_elem), f(f), root(nullptr) { n_ = 1; log_n = 0; while (n_ < n) n_ <<= 1, ++log_n; } DynamicSegmentTree(const DynamicSegmentTree & rhs) { *this = rhs; } DynamicSegmentTree(DynamicSegmentTree && rhs) { *this = std::forward<DynamicSegmentTree>(rhs); } ~DynamicSegmentTree() { clear(); } DynamicSegmentTree & operator =(const DynamicSegmentTree & rhs) { if (this != &rhs) { clear(); n = rhs.n; n_ = rhs.n_; log_n = rhs.log_n; id_elem = rhs.id_elem; f = rhs.f; root = copy_dfs(rhs.root, nullptr); } return *this; } DynamicSegmentTree & operator =(DynamicSegmentTree && rhs) { if (this != &rhs) { clear(); n = rhs.n; n_ = rhs.n_; log_n = rhs.log_n; id_elem = rhs.id_elem; f = rhs.f; root = rhs.root; rhs.root = nullptr; } return *this; } void clear() { clear_subtree(root); root = nullptr; } void clear(size_type l, size_type r) { assert(l <= r); assert(r <= size()); if ((l == 0 && r == n_) || n_ == 1) { clear(); return; } if (l == r || !root) return; std::stack<Data<node_ptr>> stk; stk.emplace(root, 0, n_); while (!stk.empty()) { auto [node, cl, cr] = stk.top(); stk.pop(); if (cl == cr) { node->val = f(node->child[0] ? node->child[0]->val : id_elem, node->child[1] ? node->child[1]->val : id_elem); continue; } const size_type m = cl + ((cr - cl) >> 1); stk.emplace(node, 0, 0); if (m < r && node->child[1]) { if (l <= m && cr <= r) { clear_subtree(node->child[1]); node->child[1] = nullptr; } else stk.emplace(node->child[1], m, cr); } if (l < m && node->child[0]) { if (l <= cl && m <= r) { clear_subtree(node->child[0]); node->child[0] = nullptr; } else stk.emplace(node->child[0], cl, m); } } } size_type size() const noexcept { return n; } void set(size_type k, const_reference x) { assert(k < size()); if (!root) root = new Node; node_ptr node = root; std::stack<node_ptr> stk; for (int i = log_n - 1; i >= 0; --i) { stk.emplace(node); const bool r = k >> i & 1; if (!node->child[r]) node->child[r] = new Node; node = node->child[r]; } node->val = x; while (!stk.empty()) { node = stk.top(); stk.pop(); node->val = f(node->child[0] ? node->child[0]->val : id_elem, node->child[1] ? node->child[1]->val : id_elem); } } value_type get(size_type k) const noexcept { assert(k < size()); if (!root) return id_elem; node_ptr node = root; for (int i = log_n - 1; i >= 0; --i) { const bool r = k >> i & 1; if (!node->child[r]) return id_elem; node = node->child[r]; } return node->val; } value_type fold(size_type l, size_type r) const noexcept { assert(l <= r); assert(r <= size()); if (l == r || !root) return id_elem; value_type res = id_elem; std::stack<Data<node_ptr>> stk; stk.emplace(root, 0, n_); while (!stk.empty()) { auto [node, cl, cr] = stk.top(); stk.pop(); if (l <= cl && cr <= r) res = f(res, node->val); else { const size_type m = cl + ((cr - cl) >> 1); if (m < r && node->child[1]) stk.emplace(node->child[1], m, cr); if (l < m && node->child[0]) stk.emplace(node->child[0], cl, m); } } return res; } value_type fold_all() const noexcept { if (!root) return id_elem; return root->val; } void swap(DynamicSegmentTree & rhs, size_type l, size_type r) { assert(size() == rhs.size()); assert(id_elem == rhs.id_elem); assert(l <= r); assert(r <= size()); if (this == &rhs) return; if (l == r) return; if ((l == 0 && r == n_) || n_ == 1) { std::swap(root, rhs.root); return; } if (!root && !rhs.root) return; if (!root) root = new Node{id_elem}; if (!rhs.root) rhs.root = new Node{id_elem}; std::stack<Data<std::pair<node_ptr, node_ptr>>> stk; stk.emplace(std::make_pair(root, rhs.root), 0, n_); while (!stk.empty()) { auto [nodes, cl, cr] = stk.top(); auto [node1, node2] = nodes; stk.pop(); if (cl == cr) { node1->val = f(node1->child[0] ? node1->child[0]->val : id_elem, node1->child[1] ? node1->child[1]->val : id_elem); node2->val = f(node2->child[0] ? node2->child[0]->val : id_elem, node2->child[1] ? node2->child[1]->val : id_elem); continue; } const size_type m = cl + ((cr - cl) >> 1); stk.emplace(nodes, 0, 0); if (m < r && (node1->child[1] || node2->child[1])) { if (l <= m && cr <= r) std::swap(node1->child[1], node2->child[1]); else { if (!node1->child[1]) node1->child[1] = new Node; else if (!node2->child[1]) node2->child[1] = new Node; stk.emplace(std::make_pair(node1->child[1], node2->child[1]), m, cr); } } if (l < m && (node1->child[0] || node2->child[0])) { if (l <= cl && m <= r) std::swap(node1->child[0], node2->child[0]); else { if (!node1->child[0]) node1->child[0] = new Node; else if (!node2->child[0]) node2->child[0] = new Node; stk.emplace(std::make_pair(node1->child[0], node2->child[0]), cl, m); } } } } private: node_ptr copy_dfs(const_ptr q, node_ptr r) { if (!q) return nullptr; node_ptr res = new Node{q->val}; res->child[0] = copy_dfs(q->child[0], res); res->child[1] = copy_dfs(q->child[1], res); return res; } void clear_subtree(node_ptr r) { if (!r) return; std::stack<node_ptr> stk; stk.emplace(r); while (!stk.empty()) { node_ptr node = stk.top(); stk.pop(); if (node->child[0]) stk.emplace(node->child[0]); if (node->child[1]) stk.emplace(node->child[1]); delete node; } } }; #line 1 "Mathematics/ModInt.hpp" #line 5 "Mathematics/ModInt.hpp" #include <iostream> #line 7 "Mathematics/ModInt.hpp" /** * @brief https://tkmst201.github.io/Library/Mathematics/ModInt.hpp */ template<int M> struct ModInt { static_assert(M > 0); using value_type = int; using calc_type = std::int_fast64_t; private: value_type val_; public: constexpr ModInt(calc_type val = 0) : val_(val % M + (val >= 0 ? 0 : M)) {} constexpr value_type val() const noexcept { return val_; } constexpr static decltype(M) mod() noexcept { return M; } explicit constexpr operator bool() const noexcept { return val_; } constexpr bool operator !() const noexcept { return !static_cast<bool>(*this); } constexpr ModInt operator +() const noexcept { return *this; } constexpr ModInt operator -() const noexcept { return ModInt(val_ == 0 ? 0 : M - val_); } constexpr ModInt operator ++(int) noexcept { ModInt res = *this; ++*this; return res; } constexpr ModInt operator --(int) noexcept { ModInt res = *this; --*this; return res; } constexpr ModInt & operator ++() noexcept { val_ = val_ + 1 == M ? 0 : val_ + 1; return *this; } constexpr ModInt & operator --() noexcept { val_ = val_ == 0 ? M - 1 : val_ - 1; return *this; } constexpr ModInt & operator +=(const ModInt & rhs) noexcept { val_ += val_ < M - rhs.val_ ? rhs.val_ : rhs.val_ - M; return *this; } constexpr ModInt & operator -=(const ModInt & rhs) noexcept { val_ += val_ >= rhs.val_ ? -rhs.val_ : M - rhs.val_; return *this; } constexpr ModInt & operator *=(const ModInt & rhs) noexcept { val_ = static_cast<calc_type>(val_) * rhs.val_ % M; return *this; } constexpr ModInt & operator /=(const ModInt & rhs) noexcept { return *this *= rhs.inv(); } friend constexpr ModInt operator +(const ModInt & lhs, const ModInt & rhs) noexcept { return ModInt(lhs) += rhs; } friend constexpr ModInt operator -(const ModInt & lhs, const ModInt & rhs) noexcept { return ModInt(lhs) -= rhs; } friend constexpr ModInt operator *(const ModInt & lhs, const ModInt & rhs) noexcept { return ModInt(lhs) *= rhs; } friend constexpr ModInt operator /(const ModInt & lhs, const ModInt & rhs) noexcept { return ModInt(lhs) /= rhs; } friend constexpr bool operator ==(const ModInt & lhs, const ModInt & rhs) noexcept { return lhs.val_ == rhs.val_; } friend constexpr bool operator !=(const ModInt & lhs, const ModInt & rhs) noexcept { return !(lhs == rhs); } friend std::ostream & operator <<(std::ostream & os, const ModInt & rhs) { return os << rhs.val_; } friend std::istream & operator >>(std::istream & is, ModInt & rhs) { calc_type x; is >> x; rhs = ModInt(x); return is; } constexpr ModInt pow(calc_type n) const noexcept { ModInt res = 1, x = val_; if (n < 0) { x = x.inv(); n = -n; } while (n) { if (n & 1) res *= x; x *= x; n >>= 1; } return res; } constexpr ModInt inv() const noexcept { value_type a = val_, a1 = 1, b = M, b1 = 0; while (b > 0) { const value_type q = a / b; value_type tmp = a - q * b; a = b; b = tmp; tmp = a1 - q * b1; a1 = b1; b1 = tmp; } assert(a == 1); if (a1 < 0) a1 += M; return a1; } }; #line 5 "Test/DynamicSegmentTree.test.cpp" #include <cstdio> int main() { int N, Q; scanf("%d %d", &N, &Q); using mint = ModInt<998244353>; using pmm = std::pair<mint, mint>; DynamicSegmentTree<pmm> seg(N, pmm(1, 0), [](const pmm & a, const pmm & b) -> pmm { return {a.first * b.first, b.first * a.second + b.second}; }); for (int i = 0; i < N; ++i) { int a, b; scanf("%d %d", &a, &b); seg.set(i, {a, b}); } while (Q--) { int q, a, b, c; scanf("%d %d %d %d", &q, &a, &b, &c); if (q == 0) { seg.set(a, {b, c}); } else { pmm v = seg.fold(a, b); mint ans = v.first * c + v.second; printf("%d\n", ans.val()); } } }