This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub gyouzasushi/library
#define PROBLEM "https://judge.yosupo.jp/problem/range_affine_point_get" #include <atcoder/modint> #include <iostream> #include "datastructure/dual_segtree.hpp" using mint = atcoder::modint998244353; struct F { mint b, c; mint val(mint x) { return b * x + c; } }; F compostition(F f, F g) { return {f.b * g.b, f.b * g.c + f.c}; } F id() { return {1, 0}; } int main() { int n, q; std::cin >> n >> q; std::vector<mint> a(n); for (int i = 0; i < n; i++) { int x; std::cin >> x; a[i] = mint::raw(x); } dual_segtree<F, compostition, id> segt(n); while (q--) { int t; std::cin >> t; if (t == 0) { int l, r; int b, c; std::cin >> l >> r >> b >> c; segt.apply(l, r, {mint::raw(b), mint::raw(c)}); } if (t == 1) { int i; std::cin >> i; std::cout << segt.get(i).val(a[i]).val() << '\n'; } } }
#line 1 "test/library-checker/range_affine_point_get.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/range_affine_point_get" #include <atcoder/modint> #include <iostream> #line 1 "datastructure/dual_segtree.hpp" #include <vector> template <class F, F (*composition)(F, F), F (*id)()> struct dual_segtree { public: dual_segtree() { } dual_segtree(int n, bool is_commutative = false) : is_commutative(is_commutative) { size = 1; height = 0; while (size < n) size <<= 1, height++; lz.assign(2 * size, id()); } void apply(int l, int r, const F &f) { l += size; r += size - 1; if (!is_commutative) thrust(l); if (!is_commutative) thrust(r); r++; while (l < r) { if (l & 1) lz[l] = composition(f, lz[l]), ++l; if (r & 1) --r, lz[r] = composition(f, lz[r]); l >>= 1, r >>= 1; } } F get(int p) { if (is_commutative) { F ret = id(); p += size; while (p > 0) { ret = composition(lz[p], ret); p >>= 1; } return ret; } else { thrust(p += size); return lz[p]; } } private: int size, height; std::vector<F> lz; bool is_commutative; inline void propagate(int k) { lz[2 * k + 0] = composition(lz[k], lz[2 * k + 0]); lz[2 * k + 1] = composition(lz[k], lz[2 * k + 1]); lz[k] = id(); } inline void thrust(int k) { for (int i = height; i > 0; i--) propagate(k >> i); } }; #line 6 "test/library-checker/range_affine_point_get.test.cpp" using mint = atcoder::modint998244353; struct F { mint b, c; mint val(mint x) { return b * x + c; } }; F compostition(F f, F g) { return {f.b * g.b, f.b * g.c + f.c}; } F id() { return {1, 0}; } int main() { int n, q; std::cin >> n >> q; std::vector<mint> a(n); for (int i = 0; i < n; i++) { int x; std::cin >> x; a[i] = mint::raw(x); } dual_segtree<F, compostition, id> segt(n); while (q--) { int t; std::cin >> t; if (t == 0) { int l, r; int b, c; std::cin >> l >> r >> b >> c; segt.apply(l, r, {mint::raw(b), mint::raw(c)}); } if (t == 1) { int i; std::cin >> i; std::cout << segt.get(i).val(a[i]).val() << '\n'; } } }