Submit Info #59861

Problem Lang User Status Time Memory
Range Affine Range Sum cpp wleungBVG AC 704 ms 18.07 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.45 MiB
max_random_00 AC 681 ms 18.07 MiB
max_random_01 AC 704 ms 18.04 MiB
max_random_02 AC 694 ms 18.04 MiB
random_00 AC 525 ms 14.27 MiB
random_01 AC 564 ms 16.50 MiB
random_02 AC 320 ms 3.74 MiB
small_00 AC 1 ms 0.45 MiB
small_01 AC 1 ms 0.45 MiB
small_02 AC 1 ms 0.45 MiB
small_03 AC 1 ms 0.45 MiB
small_04 AC 1 ms 0.46 MiB
small_05 AC 1 ms 0.41 MiB
small_06 AC 1 ms 0.45 MiB
small_07 AC 1 ms 0.45 MiB
small_08 AC 1 ms 0.45 MiB
small_09 AC 1 ms 0.45 MiB
small_random_00 AC 1 ms 0.45 MiB
small_random_01 AC 1 ms 0.41 MiB

// https://judge.yosupo.jp/problem/range_affine_range_sum #include <bits/stdc++.h> using namespace std; template<class C>constexpr int sz(const C&c){return int(c.size());} using ll=long long;constexpr const char nl='\n',sp=' '; template <class C> struct SegmentTreeLazyBottomUp { using Data = typename C::Data; using Lazy = typename C::Lazy; int N, lgN; vector<Data> TR; vector<Lazy> LZ; void apply(int i, const Lazy &v, int k) { TR[i] = C::applyLazy(TR[i], v, k); if (i < N) LZ[i] = C::mergeLazy(LZ[i], v); } void eval(int i, int k) { TR[i] = C::merge(TR[i * 2], TR[i * 2 + 1]); if (LZ[i] != C::ldef()) TR[i] = C::applyLazy(TR[i], LZ[i], k); } void propagate(int i) { int h = lgN + 1, k = 1 << lgN, ii = i >> h; for (; h > 0; ii = i >> --h, k /= 2) if (LZ[ii] != C::ldef()) { apply(ii * 2, LZ[ii], k); apply(ii * 2 + 1, LZ[ii], k); LZ[ii] = C::ldef(); } } SegmentTreeLazyBottomUp(int N) : N(N), lgN(N == 0 ? 0 : __lg(N)), TR(N * 2, C::qdef()), LZ(N, C::ldef()) {} SegmentTreeLazyBottomUp(vector<Data> A) : N(A.size()), lgN(N == 0 ? 0 : __lg(N)), TR(move(A)), LZ(N, C::ldef()) { TR.resize(N * 2, C::qdef()); copy_n(TR.begin(), N, TR.begin() + N); for (int i = N - 1; i > 0; i--) TR[i] = C::merge(TR[i * 2], TR[i * 2 + 1]); } void update(int l, int r, const Lazy &v) { propagate(l += N); propagate(r += N); bool bl = 0, br = 0; int k = 1; for (; l <= r; l /= 2, r /= 2, k *= 2) { if (bl) eval(l - 1, k); if (br) eval(r + 1, k); if (l % 2) { apply(l++, v, k); bl = 1; } if (!(r % 2)) { apply(r--, v, k); br = 1; } } for (l--, r++; r; l /= 2, r /= 2, k *= 2) { if (bl) eval(l, k); if (br && (!bl || l != r)) eval(r, k); } } Data query(int l, int r) { propagate(l += N); propagate(r += N); Data ql = C::qdef(), qr = C::qdef(); for (; l <= r; l /= 2, r /= 2) { if (l % 2) ql = C::merge(ql, TR[l++]); if (!(r % 2)) qr = C::merge(TR[r--], qr); } return C::merge(ql, qr); } }; template <class T> T addMod(T a, T b, T mod) { T ret = a + b; return ret < mod ? ret : ret - mod; } template <class T> T mulMod(T a, T b, T mod) { return a * b % mod; } const ll MOD = 998244353; struct Combine { using Data = ll; using Lazy = pair<ll, ll>; static Data qdef() { return 0; } static Lazy ldef() { return make_pair(1, 0); } static Data merge(const Data &l, const Data &r) { return addMod(l, r, MOD); } static Data applyLazy(const Data &l, const Lazy &r, int k) { return addMod(mulMod(r.first, l, MOD), mulMod(r.second, ll(k), MOD), MOD); } static Lazy mergeLazy(const Lazy &l, const Lazy &r) { return make_pair(mulMod(l.first, r.first, MOD), addMod(mulMod(l.second, r.first, MOD), r.second, MOD)); } }; int main() { // freopen("in.txt", "r", stdin); // freopen("out.txt", "w", stdout); // freopen("err.txt", "w", stderr); ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); int N, Q; cin >> N >> Q; vector<ll> A; A.reserve(N * 2); A.resize(N); for (int i = 0; i < N; i++) cin >> A[i]; SegmentTreeLazyBottomUp<Combine> ST(move(A)); for (int i = 0; i < Q; i++) { int t; cin >> t; if (t == 0) { int l, r; ll b, c; cin >> l >> r >> b >> c; ST.update(l, --r, make_pair(b, c)); } else { int l, r; cin >> l >> r; cout << ST.query(l, --r) << nl; } } return 0; }