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.yosupo.jp/problem/range_affine_point_get" #include <iostream> #include <atcoder/modint> using mint = atcoder::modint998244353; #include "library/datastructure/segment_tree/dual_segment_tree.hpp" mint mapping(std::pair<mint, mint> f, mint x) { return f.first * x + f.second; } std::pair<mint, mint> composition(std::pair<mint, mint> f, std::pair<mint, mint> g) { return { f.first * g.first, f.first * g.second + f.second }; } std::pair<mint, mint> id() { return { 1, 0 }; } using Segtree = suisen::DualSegmentTree<mint, std::pair<mint, mint>, mapping, composition, id>; int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, q; std::cin >> n >> q; std::vector<mint> a(n); for (auto &e : a) { int v; std::cin >> v; e = v; } Segtree seg(a); while (q --> 0) { int query_type; std::cin >> query_type; if (query_type == 0) { int l, r, b, c; std::cin >> l >> r >> b >> c; seg.apply(l, r, { b, c }); } else { int x; std::cin >> x; std::cout << seg.get(x).val() << '\n'; } } return 0; }
#line 1 "test/src/datastructure/segment_tree/dual_segment_tree/range_affine_point_get.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/range_affine_point_get" #include <iostream> #include <atcoder/modint> using mint = atcoder::modint998244353; #line 1 "library/datastructure/segment_tree/dual_segment_tree.hpp" #line 1 "library/datastructure/segment_tree/commutative_dual_segment_tree.hpp" #include <cassert> #include <vector> namespace suisen { template <typename T, typename F, T(*mapping)(F, T), F(*composition)(F, F), F(*id)()> struct CommutativeDualSegmentTree { CommutativeDualSegmentTree() = default; CommutativeDualSegmentTree(std::vector<T>&& a) : n(a.size()), m(ceil_pow2(a.size())), data(std::move(a)), lazy(m, id()) {} CommutativeDualSegmentTree(const std::vector<T>& a) : CommutativeDualSegmentTree(std::vector<T>(a)) {} CommutativeDualSegmentTree(int n, const T& fill_value) : CommutativeDualSegmentTree(std::vector<T>(n, fill_value)) {} T operator[](int i) const { assert(0 <= i and i < n); T res = data[i]; for (i = (i + m) >> 1; i; i >>= 1) res = mapping(lazy[i], res); return res; } T get(int i) const { return (*this)[i]; } void apply(int l, int r, const F& f) { assert(0 <= l and r <= n); for (l += m, r += m; l < r; l >>= 1, r >>= 1) { if (l & 1) apply(l++, f); if (r & 1) apply(--r, f); } } protected: int n, m; std::vector<T> data; std::vector<F> lazy; void apply(int k, const F& f) { if (k < m) { lazy[k] = composition(f, lazy[k]); } else if (k - m < n) { data[k - m] = mapping(f, data[k - m]); } } private: static int ceil_pow2(int n) { int m = 1; while (m < n) m <<= 1; return m; } }; } // namespace suisen #line 5 "library/datastructure/segment_tree/dual_segment_tree.hpp" namespace suisen { template <typename T, typename F, T(*mapping)(F, T), F(*composition)(F, F), F(*id)()> struct DualSegmentTree : public CommutativeDualSegmentTree<T, F, mapping, composition, id> { using base_type = CommutativeDualSegmentTree<T, F, mapping, composition, id>; using base_type::base_type; void apply(int l, int r, const F& f) { push(l, r); base_type::apply(l, r, f); } private: void push(int k) { base_type::apply(2 * k, this->lazy[k]), base_type::apply(2 * k + 1, this->lazy[k]); this->lazy[k] = id(); } void push(int l, int r) { const int log = __builtin_ctz(this->m); l += this->m, r += this->m; for (int i = log; i >= 1; i--) { if (((l >> i) << i) != l) push(l >> i); if (((r >> i) << i) != r) push((r - 1) >> i); } } }; template <typename T, typename F, T(*mapping)(F, T), F(*composition)(F, F), F(*id)()> DualSegmentTree(int, T)->DualSegmentTree<T, F, mapping, composition, id>; template <typename T, typename F, T(*mapping)(F, T), F(*composition)(F, F), F(*id)()> DualSegmentTree(std::vector<T>)->DualSegmentTree<T, F, mapping, composition, id>; } // namespace suisen #line 9 "test/src/datastructure/segment_tree/dual_segment_tree/range_affine_point_get.test.cpp" mint mapping(std::pair<mint, mint> f, mint x) { return f.first * x + f.second; } std::pair<mint, mint> composition(std::pair<mint, mint> f, std::pair<mint, mint> g) { return { f.first * g.first, f.first * g.second + f.second }; } std::pair<mint, mint> id() { return { 1, 0 }; } using Segtree = suisen::DualSegmentTree<mint, std::pair<mint, mint>, mapping, composition, id>; int main() { std::ios::sync_with_stdio(false); std::cin.tie(nullptr); int n, q; std::cin >> n >> q; std::vector<mint> a(n); for (auto &e : a) { int v; std::cin >> v; e = v; } Segtree seg(a); while (q --> 0) { int query_type; std::cin >> query_type; if (query_type == 0) { int l, r, b, c; std::cin >> l >> r >> b >> c; seg.apply(l, r, { b, c }); } else { int x; std::cin >> x; std::cout << seg.get(x).val() << '\n'; } } return 0; }