Submit Info #3012

Problem Lang User Status Time Memory
Range Affine Range Sum cpp spihill AC 1383 ms 17.01 MiB

ケース詳細
Name Status Time Memory
example_00 AC 4 ms 0.62 MiB
max_random_00 AC 1341 ms 16.96 MiB
max_random_01 AC 1349 ms 17.01 MiB
max_random_02 AC 1383 ms 17.00 MiB
random_00 AC 1018 ms 16.16 MiB
random_01 AC 1095 ms 16.43 MiB
random_02 AC 688 ms 4.17 MiB
small_00 AC 8 ms 0.68 MiB
small_01 AC 7 ms 0.62 MiB
small_02 AC 8 ms 0.62 MiB
small_03 AC 8 ms 0.64 MiB
small_04 AC 6 ms 0.62 MiB
small_05 AC 8 ms 0.59 MiB
small_06 AC 7 ms 0.68 MiB
small_07 AC 6 ms 0.62 MiB
small_08 AC 9 ms 0.63 MiB
small_09 AC 6 ms 0.62 MiB
small_random_00 AC 8 ms 0.68 MiB
small_random_01 AC 10 ms 0.69 MiB

#define PROBLEM "https://judge.yosupo.jp/problem/range_affine_range_sum" #include<bits/stdc++.h> using namespace std; // #include "../../datastructure/SegmentTree/LazySegmentTree.cpp" // #include "../../monoid/pair/plus_affine_monoid.cpp" // #include "../../math/ModInt.cpp" /** * @title 遅延伝播セグメント木 * @brief 0-indexed 半開区間 * @brief MonoidPair はクラス Node と クラス Lazy を持つ。 * @brief クラス Node と Lazy は Monoid であり、{型(monoid_type), 演算(operator+), 単位元(default constructor), constructor(monoid_type)} の4つを持つ。 * @brief クラス Lazy は {operator*(int), is_unity()} も持つ。 * @brief クラス Node は operator+(const Lazy&) も持つ。 * @brief MonoidPair の具体例は monoid/pair/ にある。 */ template<class MonoidPair> struct LazySegmentTree { int n; using Node = typename MonoidPair::Node; using Node_T = typename MonoidPair::Node::monoid_type; using Lazy = typename MonoidPair::Lazy; using Lazy_T = typename MonoidPair::Lazy::monoid_type; vector<Node> node; vector<Lazy> lazy; // @brief サイズ N で初期化(初期値は単位元) O(N)$ LazySegmentTree (int N) {build(N);} // @brief vector で初期化 O(N)$ LazySegmentTree (const vector<Node_T>& v) {build(v);} LazySegmentTree () {} // @brief (a, b] に x を遅延伝播 O(\log N)$ void set(int a, int b, Lazy_T x) {set(a, b, x, 0, 0, n);} // @brief (a, b] を取得 O(\log N)$ Node_T get(int a, int b) {return get(a, b, 0, 0, n).val;} // @brief index i を取得 O(\log N)$ const Node_T& operator[](int i) { return get(i, i+1); } // @brief サイズ N で再構築(初期値は単位元) O(N)$ void build(int n_) { n = calc_n(n_); node.clear(); node.resize(2*n-1); lazy.clear(); lazy.resize(2*n-1); } // @brief vector で再構築 O(N)$ void build(const vector<Node_T>& v) { build(v.size()); for (size_t i = 0; i < v.size(); i++) { node[i+n-1].val = v[i]; } for (int i = n - 2; i >= 0; i--){ node[i] = node[i*2+1] + node[i*2+2]; } } private: void eval(int len, int k) { if (lazy[k].is_unity()) return; if (2*k+1 < 2*n-1) { lazy[2*k+1] = lazy[2*k+1] + lazy[k]; lazy[2*k+2] = lazy[2*k+2] + lazy[k]; } node[k] = node[k] + lazy[k] * len; lazy[k] = Lazy(); } Node set(int a, int b, Lazy_T x, int k, int l, int r) { eval(r-l, k); if (r <= a || b <= l) return node[k]; if (a <= l && r <= b) { lazy[k] = lazy[k] + Lazy(x); return node[k] + lazy[k] * (r-l); } return node[k] = set(a, b, x, 2*k+1, l, (l+r) / 2) + set(a, b, x, 2*k+2, (l+r) / 2, r); } Node get(int a, int b, int k, int l, int r) { eval(r-l, k); if (a <= l && r <= b) { return node[k]; } else if (b <= l || r <= a) { return Node(); } return get(a, b, 2*k+1, l, (l+r) / 2) + get(a, b, 2*k+2, (l+r) / 2, r); } int calc_n(int n_, int t = 1) {return n_ > t ? calc_n(n_, t << 1) : t;} }; /** * @title ModInt * @brief mod を取りながら計算する。リテラル型の要件を満たし、constexprに対応している。 * @brief これでも Verify してます。 https://github.com/spihill/library/blob/master/test/mytest/ModInt.test.cpp */ namespace mylib { template<int mod> struct ModInt { using i64 = int_fast64_t; int x; constexpr static int get_mod() { return mod; } constexpr ModInt(i64 x_) : x(mod_(x_)) {} constexpr ModInt() : ModInt(0) {} ~ModInt() = default; inline constexpr ModInt& operator+=(const ModInt rhs) { i64 t = static_cast<i64>(x) + rhs.x; if (t >= mod) x = t - mod; else x = t; return (*this); } inline constexpr ModInt& operator-=(const ModInt rhs) { i64 t = static_cast<i64>(x) + mod - rhs.x; if (t >= mod) x = t - mod; else x = t; return *this; } inline constexpr ModInt& operator*=(const ModInt rhs) { x = static_cast<i64>(x) * rhs.x % mod; return *this; } inline constexpr ModInt& operator/=(ModInt rhs) { return *this *= rhs.inv(); } inline constexpr ModInt power(i64 p) const { ModInt res = 1; ModInt a = x; for (; p; res = p & 1 ? res * a : res, a *= a, p >>= 1); return res; } inline constexpr ModInt inv() const { int z = 0, w = 0; extgcd(mod, x, z, w); return ModInt(w); } inline constexpr ModInt& operator=(const ModInt& rhs) { this->x = rhs.x; return *this; } inline constexpr int operator==(const ModInt& rhs) const { return this->x == rhs.x; } inline constexpr int operator!=(const ModInt& rhs) const { return !(*this == rhs); } inline constexpr ModInt operator++(signed unused) { ModInt res(*this); ++(*this); return res; } inline constexpr ModInt& operator++() { (*this) += 1; return (*this); } inline constexpr ModInt operator--(signed unused) { ModInt res(*this); --(*this); return res; } inline constexpr ModInt& operator--() { (*this) -= 1; return (*this); } inline constexpr ModInt operator+() const { return (*this); } inline constexpr ModInt operator-() const { return (*this).x ? ModInt(mod - (*this).x) : ModInt(0); } friend constexpr ModInt operator+(const ModInt& lhs, const ModInt& rhs) {return ModInt(lhs) += rhs;} friend constexpr ModInt operator-(const ModInt& lhs, const ModInt& rhs) {return ModInt(lhs) -= rhs;} friend constexpr ModInt operator*(const ModInt& lhs, const ModInt& rhs) {return ModInt(lhs) *= rhs;} friend constexpr ModInt operator/(const ModInt& lhs, const ModInt& rhs) {return ModInt(lhs) /= rhs;} explicit constexpr operator int() const {return x;} friend ostream& operator<<(ostream& lhs, const ModInt& rhs) { lhs << rhs.x; return lhs; } friend istream& operator>>(istream& lhs, ModInt& rhs) { i64 t; lhs >> t; rhs = ModInt(t); return lhs; } private: constexpr int extgcd(int a, int b, int& x, int& y) const { int d = a; if (b == 0) { x = 1; y = 0; } else { d = extgcd(b, a%b, y, x); y -= a / b * x; } return d; } constexpr int mod_(i64 x) { x %= mod; if (x < 0) x += mod; return static_cast<int>(x); } }; }; // mylib using namespace mylib; using modint = ModInt<998244353>; template<class T> struct plus_monoid { using mono = plus_monoid; plus_monoid() : plus_monoid(T()) {} explicit plus_monoid(T x) : val(x) {} T val; mono operator+(const mono& rhs) const { return mono(val + rhs.val); } friend istream& operator>>(istream& lhs, mono& rhs) { lhs >> rhs.val; return lhs; } friend ostream& operator<<(ostream& lhs, mono& rhs) { lhs << rhs.val; return lhs; } using monoid_type = T; }; template<class T> struct affine_monoid { using mono = affine_monoid; affine_monoid() : affine_monoid(pair<T, T>(1, 0)) {} explicit affine_monoid(pair<T, T> x) : val(x) {} pair<T, T> val; mono operator+(const mono& rhs) const { return mono(pair<T, T>(rhs.val.first * val.first, rhs.val.first * val.second + rhs.val.second)); } friend istream& operator>>(istream& lhs, mono& rhs) { lhs >> rhs.val.first >> rhs.val.second; return lhs; } friend ostream& operator<<(ostream& lhs, mono& rhs) { lhs << rhs.val.first << ' ' << rhs.val.second; return lhs; } using monoid_type = pair<T, T>; }; template<class T, class U = T> struct plus_affine_monoid { template<class TT> using lazy_monoid = affine_monoid<TT>; template<class TT> using node_monoid = plus_monoid<TT>; struct Lazy : public lazy_monoid<U> { using lazy_monoid<U>::lazy_monoid; using lazy_monoid<U>::operator+; using lazy_monoid<U>::operator=; Lazy(lazy_monoid<U> x) : lazy_monoid<U>(x) {} inline Lazy operator*(int len) const { return Lazy(make_pair(this->val.first, this->val.second * len)); } inline bool is_unity() const { return this->val == make_pair<U, U>(1, 0); } }; struct Node : public node_monoid<T> { using node_monoid<T>::node_monoid; using node_monoid<T>::operator+; using node_monoid<T>::operator=; Node(node_monoid<T> x) : node_monoid<T>(x) {} inline Node operator+(const Lazy& rhs) const { return Node(this->val * rhs.val.first + rhs.val.second); } }; }; using monoid = plus_affine_monoid<modint>; int main() { std::ios::sync_with_stdio(false), std::cin.tie(nullptr); int N, Q; cin >> N >> Q; vector<modint> v(N); for (int i = 0; i < N; i++) cin >> v[i]; LazySegmentTree<monoid> Seg(v); for (int i = 0; i < Q; i++) { int q; cin >> q; if (q == 0) { int l, r, b, c; cin >> l >> r >> b >> c; Seg.set(l, r, {b, c}); } else { int l, r; cin >> l >> r; cout << Seg.get(l, r) << endl; } } }