Problems Submissions
Register Login 質問(Gitter) GitHub

Submit Info #3674

Problem Lang User Status Time Memory
Range Affine Range Sum cpp noshi91 AC 650 ms 33.75 MiB

ケース詳細
Name Status Time Memory
example_00 AC 5 ms 0.62 MiB
max_random_00 AC 645 ms 33.66 MiB
max_random_01 AC 646 ms 33.67 MiB
max_random_02 AC 650 ms 33.75 MiB
random_00 AC 502 ms 26.50 MiB
random_01 AC 526 ms 31.00 MiB
random_02 AC 276 ms 5.80 MiB
small_00 AC 7 ms 0.55 MiB
small_01 AC 4 ms 0.62 MiB
small_02 AC 5 ms 0.66 MiB
small_03 AC 7 ms 0.55 MiB
small_04 AC 5 ms 0.66 MiB
small_05 AC 5 ms 0.55 MiB
small_06 AC 6 ms 0.64 MiB
small_07 AC 5 ms 0.62 MiB
small_08 AC 5 ms 0.55 MiB
small_09 AC 7 ms 0.64 MiB
small_random_00 AC 6 ms 0.59 MiB
small_random_01 AC 5 ms 0.68 MiB

#define NDEBUG #line 1 "test/lazy_segment_tree.yosupo.test.cpp" #define PROBLEM "https://judge.yosupo.jp/problem/range_affine_range_sum" #line 1 "data_structure/lazy_segment_tree.cpp" #include <cassert> #include <cstddef> #include <vector> template <class A> class lazy_segment_tree { using size_t = std::size_t; using V = typename A::value_structure; using T = typename V::value_type; using O = typename A::operator_structure; using E = typename O::value_type; class node_type { public: T value; E lazy; node_type(const T &value, const E &lazy) : value(value), lazy(lazy) {} }; static size_t lsb(const size_t x) { return __builtin_ctz(x); } static size_t msb(const size_t x) { return 31 - __builtin_clz(x); } static T get(const node_type &x) { return x.value; } static void add(node_type &x, const E &y) { x.value = A::operation(x.value, y); x.lazy = O::operation(x.lazy, y); } std::vector<node_type> tree; void propagate(const size_t index) { add(tree[index * 2], tree[index].lazy); add(tree[index * 2 + 1], tree[index].lazy); tree[index].lazy = O::identity; } void propagate_bound(const size_t index) { if (index == 0) return; const size_t lsb_ = lsb(index); for (size_t h = msb(index); h != lsb_; h -= 1) propagate(index >> h); } void recalc(const size_t index) { tree[index].value = V::operation(get(tree[index * 2]), get(tree[index * 2 + 1])); } void recalc_bound(size_t index) { if (index == 0) return; index >>= lsb(index); while (index != 1) { index /= 2; recalc(index); } } public: lazy_segment_tree() = default; explicit lazy_segment_tree(const size_t n) : tree(n * 2, node_type(V::identity, O::identity)) {} void set_unsafe(const size_t index, const T &x) { tree[index + size()].value = x; } void build_unsafe() { for (size_t i = size(); i != 1;) { i -= 1; tree[i].value = V::operation(tree[i * 2].value, tree[i * 2 + 1].value); } } size_t size() const { return tree.size() / 2; } T fold(size_t first, size_t last) { assert(first <= last); assert(last <= size()); first += size(); last += size(); propagate_bound(first); recalc_bound(first); propagate_bound(last); recalc_bound(last); T fold_l = V::identity; T fold_r = V::identity; while (first != last) { if (first % 2 != 0) { fold_l = V::operation(fold_l, get(tree[first])); first += 1; } first /= 2; if (last % 2 != 0) { last -= 1; fold_r = V::operation(get(tree[last]), fold_r); } last /= 2; } return V::operation(fold_l, fold_r); } void update_range(size_t first, size_t last, const E &x) { assert(first <= last); assert(last <= size()); first += size(); last += size(); propagate_bound(first); propagate_bound(last); const size_t first_c = first; const size_t last_c = last; while (first != last) { if (first % 2 != 0) { add(tree[first], x); first += 1; } first /= 2; if (last % 2 != 0) { last -= 1; add(tree[last], x); } last /= 2; } recalc_bound(first_c); recalc_bound(last_c); } void update_point(size_t index, const T &x) { assert(index < size()); index += size(); for (size_t h = msb(index); h != 0; h -= 1) propagate(index >> h); tree[index] = node_type(x, O::identity); while (index != 1) { index /= 2; recalc(index); } } }; #line 1 "other/modint.cpp" #include <cstdint> template <std::uint_fast64_t Modulus> class modint { using u64 = std::uint_fast64_t; public: using value_type = u64; static constexpr u64 mod = Modulus; private: static_assert(mod < static_cast<u64>(1) << 32, "Modulus must be less than 2**32"); u64 v; constexpr modint &negate() noexcept { if (v != 0) v = mod - v; return *this; } public: constexpr modint(const u64 x = 0) noexcept : v(x % mod) {} constexpr u64 &value() noexcept { return v; } constexpr const u64 &value() const noexcept { return v; } constexpr modint operator+() const noexcept { return modint(*this); } constexpr modint operator-() const noexcept { return modint(*this).negate(); } constexpr modint operator+(const modint rhs) const noexcept { return modint(*this) += rhs; } constexpr modint operator-(const modint rhs) const noexcept { return modint(*this) -= rhs; } constexpr modint operator*(const modint rhs) const noexcept { return modint(*this) *= rhs; } constexpr modint operator/(const modint rhs) const noexcept { return modint(*this) /= rhs; } constexpr modint &operator+=(const modint rhs) noexcept { v += rhs.v; if (v >= mod) v -= mod; return *this; } constexpr modint &operator-=(const modint rhs) noexcept { if (v < rhs.v) v += mod; v -= rhs.v; return *this; } constexpr modint &operator*=(const modint rhs) noexcept { v = v * rhs.v % mod; return *this; } constexpr modint &operator/=(modint rhs) noexcept { u64 exp = mod - 2; while (exp != 0) { if (exp % 2 != 0) *this *= rhs; rhs *= rhs; exp /= 2; } return *this; } }; template <std::uint_fast64_t Modulus> constexpr typename modint<Modulus>::u64 modint<Modulus>::mod; #line 1 "other/affine.cpp" template <class T> class affine { public: T a; T b; constexpr affine(const T &a = 1, const T &b = 0) noexcept : a(a), b(b) {} constexpr T evaluate(const T &x) const noexcept { return x * a + b; } friend constexpr affine operator+(const affine &l, const affine &r) noexcept { return affine(l.a + r.a, l.b + r.b); } constexpr affine composite(const affine &r) const noexcept { return affine(a * r.a, b * r.a + r.b); } }; template <class T> class affine_composite_monoid { public: using value_type = affine<T>; static constexpr value_type operation(const value_type &l, const value_type &r) noexcept { return l.composite(r); } static constexpr value_type identity{}; }; #line 1 "other/cartesian_product_monoid.cpp" #include <utility> template <class M, class N> class cartesian_product_monoid { using T = std::pair<typename M::value_type, typename N::value_type>; public: using value_type = T; static constexpr T operation(const T &l, const T &r) noexcept { return T(M::operation(l.first, r.first), N::operation(l.second, r.second)); } static constexpr T identity{M::identity, N::identity}; }; #line 1 "other/plus_monoid.cpp" template <class T> class plus_monoid { public: using value_type = T; static T operation(const T l, const T r) { return l + r; } static constexpr T identity = 0; }; #line 4 "other/sum_affine_action.cpp" template <class T> class sum_affine_action { public: using value_structure = cartesian_product_monoid<plus_monoid<T>, plus_monoid<T>>; using operator_structure = affine_composite_monoid<T>; private: using U = typename value_structure::value_type; using E = typename operator_structure::value_type; public: static constexpr U operation(const U &l, const E &r) { return U(l.first * r.a + l.second * r.b, l.second); } }; #line 6 "test/lazy_segment_tree.yosupo.test.cpp" /* https://atcoder.jp/contests/abc153/submissions/9767872 */ #include <cstdio> const int cm = 1 << 17; char cn[cm], *ci = cn + cm, ct; inline char getcha() { if (ci - cn == cm) { fread_unlocked(cn, 1, cm, stdin); ci = cn; } return *ci++; } inline int getint() { int A = 0; if (ci - cn + 16 > cm) while ((ct = getcha()) >= '0') A = A * 10 + ct - '0'; else while ((ct = *ci++) >= '0') A = A * 10 + ct - '0'; return A; } /* https://atcoder.jp/contests/abc153/submissions/9767872 */ int main() { using mint = modint<998244353>; const int n = getint(); const int q = getint(); lazy_segment_tree<sum_affine_action<mint>> lst(n); for (int i = 0; i != n; i += 1) lst.set_unsafe(i, {getint(), 1}); lst.build_unsafe(); for (int i = 0; i != q; i += 1) { switch (getint()) { case 0: { const int l = getint(); const int r = getint(); const int b = getint(); const int c = getint(); lst.update_range(l, r, {b, c}); } break; case 1: { const int l = getint(); const int r = getint(); printf("%d\n", (int)lst.fold(l, r).first.value()); } break; } } }