Submit Info #21201

Problem Lang User Status Time Memory
Range Affine Range Sum cpp wleungBVG AC 699 ms 18.30 MiB

ケース詳細
Name Status Time Memory
example_00 AC 2 ms 0.67 MiB
max_random_00 AC 688 ms 18.12 MiB
max_random_01 AC 695 ms 18.30 MiB
max_random_02 AC 699 ms 18.30 MiB
random_00 AC 530 ms 14.55 MiB
random_01 AC 561 ms 16.80 MiB
random_02 AC 324 ms 4.13 MiB
small_00 AC 1 ms 0.61 MiB
small_01 AC 1 ms 0.67 MiB
small_02 AC 2 ms 0.67 MiB
small_03 AC 1 ms 0.64 MiB
small_04 AC 1 ms 0.67 MiB
small_05 AC 3 ms 0.67 MiB
small_06 AC 2 ms 0.66 MiB
small_07 AC 0 ms 0.66 MiB
small_08 AC 2 ms 0.67 MiB
small_09 AC 3 ms 0.71 MiB
small_random_00 AC 1 ms 0.62 MiB
small_random_01 AC 2 ms 0.67 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], C::getSegmentVal(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], C::getSegmentVal(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(); } } template <class F> SegmentTreeLazyBottomUp(int N, F f) : N(N), lgN(N == 0 ? 0 : __lg(N)), TR(N * 2, C::qdef()), LZ(N, C::ldef()) { generate(TR.begin() + N, TR.end(), f); for (int i = N - 1; i > 0; i--) TR[i] = C::merge(TR[i * 2], TR[i * 2 + 1]); } template <class It> SegmentTreeLazyBottomUp(It st, It en) : SegmentTreeLazyBottomUp(en - st, [&] { return *st++; }) {} SegmentTreeLazyBottomUp(int N, const Data &vdef) : SegmentTreeLazyBottomUp(N, [&] { return vdef; }) {} 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) { return addMod(mulMod(r.first, l, MOD), r.second, MOD); } static Lazy getSegmentVal(const Lazy &v, int k) { return make_pair(v.first, mulMod(v.second, ll(k), 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; SegmentTreeLazyBottomUp<Combine> ST(N, [&] { ll a; cin >> a; return 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; }