Submit Info #54153

Problem Lang User Status Time Memory
Range Affine Range Sum cpp nor AC 426 ms 16.97 MiB

ケース詳細
Name Status Time Memory
example_00 AC 1 ms 0.61 MiB
max_random_00 AC 418 ms 16.97 MiB
max_random_01 AC 418 ms 16.96 MiB
max_random_02 AC 426 ms 16.96 MiB
random_00 AC 323 ms 16.20 MiB
random_01 AC 343 ms 16.46 MiB
random_02 AC 198 ms 4.21 MiB
small_00 AC 1 ms 0.71 MiB
small_01 AC 1 ms 0.71 MiB
small_02 AC 1 ms 0.72 MiB
small_03 AC 1 ms 0.71 MiB
small_04 AC 1 ms 0.72 MiB
small_05 AC 1 ms 0.71 MiB
small_06 AC 1 ms 0.71 MiB
small_07 AC 1 ms 0.71 MiB
small_08 AC 1 ms 0.71 MiB
small_09 AC 1 ms 0.70 MiB
small_random_00 AC 1 ms 0.71 MiB
small_random_01 AC 1 ms 0.71 MiB

#pragma GCC optimize("O3,unroll-loops") #pragma GCC target("avx,avx2,sse,sse2,sse3,sse4,popcnt") #include <bits/stdc++.h> using namespace std; namespace IO { constexpr bool UNSAFE = false; constexpr int GLOB_BUF_SIZE = 1 << 15; #ifndef DEBUG #define CHANGE_DEFAULT_STREAMS static struct FastInput { FastInput() { if constexpr (UNSAFE) { chars_read = fread(buf, 1, BUF_SIZE, in); buf_pos = 0; buf[0] = (chars_read == 0 ? -1 : buf[0]); } } static constexpr int BUF_SIZE = GLOB_BUF_SIZE; char buf[BUF_SIZE]; size_t chars_read = 0; size_t buf_pos = 0; FILE* in = stdin; char cur = 0; inline char get_char() { if constexpr (!UNSAFE) { if (buf_pos >= chars_read) { chars_read = fread(buf, 1, BUF_SIZE, in); buf_pos = 0; buf[0] = (chars_read == 0 ? -1 : buf[0]); } } return cur = buf[buf_pos++]; } template <typename T> inline FastInput* tie(T) { return this; } inline void sync_with_stdio(bool) {} inline explicit operator bool() { return cur != -1; } inline static bool is_blank(char c) { return c <= ' '; } inline bool skip_blanks() { while (is_blank(cur) && cur != -1) get_char(); return cur != -1; } inline FastInput& operator>>(char& c) { skip_blanks(); c = cur; return *this; } inline FastInput& operator>>(std::string& s) { if (skip_blanks()) { s.clear(); do { s += cur; } while (!is_blank(get_char())); } return *this; } template <typename T> inline FastInput& read_integer(T& n) { // unsafe, doesn't check that characters are actually digits n = 0; if (skip_blanks()) { int sign = +1; if (cur == '-') { sign = -1; get_char(); } do { n += n + (n << 3) + cur - '0'; } while (!is_blank(get_char())); n *= sign; } return *this; } template <typename T> inline typename std::enable_if<std::is_integral<T>::value, FastInput&>::type operator>>(T& n) { return read_integer(n); } #if !defined(_WIN32) || defined(_WIN64) inline FastInput& operator>>(__int128& n) { return read_integer(n); } #endif template <typename T> inline typename std::enable_if<std::is_floating_point<T>::value, FastInput&>::type operator>>(T& n) { // not sure if really fast, for compatibility only n = 0; if (skip_blanks()) { std::string s; (*this) >> s; sscanf(s.c_str(), "%lf", &n); } return *this; } } fast_input; #define cin IO::fast_input static struct FastOutput { static constexpr int BUF_SIZE = GLOB_BUF_SIZE; char buf[BUF_SIZE]; size_t buf_pos = 0; static constexpr int TMP_SIZE = GLOB_BUF_SIZE; char tmp[TMP_SIZE]; FILE* out = stdout; inline void put_char(char c) { buf[buf_pos++] = c; if (buf_pos == BUF_SIZE) { fwrite(buf, 1, buf_pos, out); buf_pos = 0; } } ~FastOutput() { fwrite(buf, 1, buf_pos, out); } inline FastOutput& operator<<(char c) { put_char(c); return *this; } inline FastOutput& operator<<(const char* s) { while (*s) put_char(*s++); return *this; } inline FastOutput& operator<<(const std::string& s) { for (auto x : s) put_char(x); return *this; } template <typename T> inline char* integer_to_string(T n) { // beware of TMP_SIZE char* p = tmp + TMP_SIZE - 1; if (n == 0) *--p = '0'; else { bool is_negative = false; if (n < 0) { is_negative = true; n = -n; } while (n > 0) { *--p = (char)('0' + n % 10); n /= 10; } if (is_negative) *--p = '-'; } return p; } template <typename T> inline typename std::enable_if<std::is_integral<T>::value, char*>::type stringify(T n) { return integer_to_string(n); } #if !defined(_WIN32) || defined(_WIN64) inline char* stringify(__int128 n) { return integer_to_string(n); } #endif template <typename T> inline typename std::enable_if<std::is_floating_point<T>::value, char*>::type stringify(T n) { sprintf(tmp, "%.17f", n); return tmp; } template <typename T> inline FastOutput& operator<<(const T& n) { auto p = stringify(n); for (; *p != 0; p++) put_char(*p); return *this; } } fast_output; #define cout IO::fast_output #endif } // namespace IO // clang-format off template <class Base, class Node, class Update, class MakeNode, class CombineNodes, class ApplyUpdate, class ComposeUpdates = std::nullptr_t> struct lazy_segtree { static constexpr bool is_lazy = !std::is_same<ComposeUpdates, std::nullptr_t>::value; public: template <typename... T> explicit lazy_segtree(int n, const Base& id_base, T... args) : lazy_segtree(std::vector<Base>(n, id_base), args...) {} explicit lazy_segtree(const std::vector<Base>& v, const Node& _id_node, const MakeNode& _make_node, const CombineNodes& _combine, const Update& _id_update, const ApplyUpdate& _apply_update, const ComposeUpdates& _compose_updates = nullptr) : _n(int(v.size())), make_node(_make_node), combine(_combine), id_node(_id_node), apply_update(_apply_update), id_update(_id_update), compose_updates(_compose_updates) { build(v); } void build(const std::vector<Base>& v) { _n = int(v.size()); log = 0; while ((1 << log) < _n) ++log; size = 1 << log; d = std::vector<Node>(2 * size, id_node); if constexpr (is_lazy) lz = std::vector<Update>(size, id_update); for (int i = 0; i < _n; i++) d[size + i] = make_node(v[i], i); for (int i = size - 1; i >= 1; i--) update(i); } void set(int p, Node x) { p += size; if constexpr (is_lazy) for (int i = log; i >= 1; i--) push(p >> i); d[p] = x; for (int i = 1; i <= log; ++i) update(p >> i); } Node get(int p) { p += size; if constexpr (is_lazy) for (int i = log; i >= 1; i--) push(p >> i); return d[p]; } Node query(int l, int r) { if (l == r) return id_node; l += size, r += size; if constexpr (is_lazy) { int l_ctz = __builtin_ctz(l); int r_ctz = __builtin_ctz(r); for (int i = log; i > l_ctz; --i) push(l >> i); for (int i = log; i > r_ctz; --i) push((r - 1) >> i); } Node sml = id_node, smr = id_node; while (l < r) { if (l & 1) sml = combine(sml, d[l++]); if (r & 1) smr = combine(d[--r], smr); l >>= 1, r >>= 1; } return combine(sml, smr); } Node all_query() const { return d[1]; } void update(int p, Update f) { p += size; if constexpr (is_lazy) for (int i = log; i >= 1; i--) push(p >> i); d[p] = apply_update(f, d[p]); for (int i = 1; i <= log; ++i) update(p >> i); } void update(int l, int r, Update f) { if (l == r) return; l += size, r += size; const int l_ctz = __builtin_ctz(l); const int r_ctz = __builtin_ctz(r); if constexpr (is_lazy) { for (int i = log; i > l_ctz; --i) push(l >> i); for (int i = log; i > r_ctz; --i) push((r - 1) >> i); } { const int l2 = l, r2 = r; while (l < r) { if (l & 1) all_apply(l++, f); if (r & 1) all_apply(--r, f); l >>= 1, r >>= 1; } l = l2, r = r2; } for (int i = l_ctz + 1; i <= log; ++i) update(l >> i); for (int i = r_ctz + 1; i <= log; ++i) update((r - 1) >> i); } template <class G> int max_right(int l, G g) { // assert(0 <= l && l <= _n); // assert(g(id_node)); if (l == _n) return _n; l += size; if constexpr (is_lazy) for (int i = log; i >= 1; i--) push(l >> i); Node sm = id_node; do { while (l % 2 == 0) l >>= 1; if (!g(combine(sm, d[l]))) { while (l < size) { if constexpr (is_lazy) push(l); l = (2 * l); if (g(combine(sm, d[l]))) { sm = combine(sm, d[l]); l++; } } return l - size; } sm = combine(sm, d[l]); l++; } while ((l & -l) != l); return _n; } template <class G> int min_left(int r, G g) { // assert(0 <= r && r <= _n); // assert(g(id_node)); if (r == 0) return 0; r += size; if constexpr (is_lazy) for (int i = log; i >= 1; i--) push((r - 1) >> i); Node sm = id_node; do { r--; while (r > 1 && (r % 2)) r >>= 1; if (!g(combine(d[r], sm))) { while (r < size) { if constexpr (is_lazy) push(r); r = (2 * r + 1); if (g(combine(d[r], sm))) { sm = combine(d[r], sm); r--; } } return r + 1 - size; } sm = combine(d[r], sm); } while ((r & -r) != r); return 0; } private: int _n, size, log; std::vector<Node> d; std::vector<Update> lz; MakeNode make_node; CombineNodes combine; Node id_node; ApplyUpdate apply_update; Update id_update; ComposeUpdates compose_updates; void update(int k) { d[k] = combine(d[2 * k], d[2 * k + 1]); } void all_apply(int k, Update f) { d[k] = apply_update(f, d[k]); if constexpr (is_lazy) if (k < size) lz[k] = compose_updates(f, lz[k]); } void push(int k) { all_apply(2 * k, lz[k]); all_apply(2 * k + 1, lz[k]); lz[k] = id_update; } }; // clang-format on using namespace std; constexpr int mod = int(1e9) + 7; constexpr int nttmod = 998'244'353; template <uint32_t mod> struct LazyMontgomeryModInt { using mint = LazyMontgomeryModInt; using i32 = int32_t; using u32 = uint32_t; using u64 = uint64_t; static constexpr u32 get_r() { u32 ret = mod; for (i32 i = 0; i < 4; ++i) ret *= 2 - mod * ret; return ret; } static constexpr u32 r = get_r(); static constexpr u32 n2 = -u64(mod) % mod; static_assert(r * mod == 1, "invalid, r * mod != 1"); static_assert(mod < (1 << 30), "invalid, mod >= 2 ^ 30"); static_assert((mod & 1) == 1, "invalid, mod % 2 == 0"); u32 a; constexpr LazyMontgomeryModInt() : a(0) {} constexpr LazyMontgomeryModInt(const int64_t& b) : a(reduce(u64(b % mod + mod) * n2)){}; static constexpr u32 reduce(const u64& b) { return (b + u64(u32(b) * u32(-r)) * mod) >> 32; } constexpr mint& operator+=(const mint& b) { if (i32(a += b.a - 2 * mod) < 0) a += 2 * mod; return *this; } constexpr mint& operator-=(const mint& b) { if (i32(a -= b.a) < 0) a += 2 * mod; return *this; } constexpr mint& operator*=(const mint& b) { a = reduce(u64(a) * b.a); return *this; } constexpr mint& operator/=(const mint& b) { *this *= b.inverse(); return *this; } constexpr mint operator+(const mint& b) const { return mint(*this) += b; } constexpr mint operator-(const mint& b) const { return mint(*this) -= b; } constexpr mint operator*(const mint& b) const { return mint(*this) *= b; } constexpr mint operator/(const mint& b) const { return mint(*this) /= b; } constexpr bool operator==(const mint& b) const { return (a >= mod ? a - mod : a) == (b.a >= mod ? b.a - mod : b.a); } constexpr bool operator!=(const mint& b) const { return (a >= mod ? a - mod : a) != (b.a >= mod ? b.a - mod : b.a); } constexpr mint operator-() const { return mint() - mint(*this); } constexpr mint pow(u64 n) const { mint ret(1), mul(*this); while (n > 0) { if (n & 1) ret *= mul; mul *= mul; n >>= 1; } return ret; } constexpr mint inverse() const { return pow(mod - 2); } template <class T> friend T& operator<<(T& os, const mint& b) { return os << b.get(); } template <class T> friend T& operator>>(T& is, mint& b) { int64_t t; is >> t; b = LazyMontgomeryModInt<mod>(t); return (is); } constexpr u32 get() const { u32 ret = reduce(a); return ret >= mod ? ret - mod : ret; } static constexpr u32 get_mod() { return mod; } }; template <uint32_t Modulus> class Modular { using M = Modular; public: static_assert(int(Modulus) >= 1, "Modulus must be in the range [1, 2^31)"); static constexpr int modulus() { return Modulus; } static M raw(uint32_t v) { return *reinterpret_cast<M*>(&v); } Modular() : v_(0) {} Modular(int64_t v) : v_((v %= Modulus) < 0 ? v + Modulus : v) {} template <class T> explicit operator T() const { return v_; } M& operator++() { return v_ = ++v_ == Modulus ? 0 : v_, *this; } M& operator--() { return --(v_ ? v_ : v_ = Modulus), *this; } M& operator*=(M o) { return v_ = uint64_t(v_) * o.v_ % Modulus, *this; } M& operator/=(M o) { auto [inv, gcd] = extgcd(o.v_, Modulus); assert(gcd == 1); return *this *= inv; } M& operator+=(M o) { return v_ = int(v_ += o.v_ - Modulus) < 0 ? v_ + Modulus : v_, *this; } M& operator-=(M o) { return v_ = int(v_ -= o.v_) < 0 ? v_ + Modulus : v_, *this; } friend M operator++(M& a, int) { return exchange(a, ++M(a)); } friend M operator--(M& a, int) { return exchange(a, --M(a)); } friend M operator+(M a) { return a; } friend M operator-(M a) { return a.v_ = a.v_ ? Modulus - a.v_ : 0, a; } friend M operator*(M a, M b) { return a *= b; } friend M operator/(M a, M b) { return a /= b; } friend M operator+(M a, M b) { return a += b; } friend M operator-(M a, M b) { return a -= b; } friend istream& operator>>(istream& is, M& x) { int64_t v; return is >> v, x = v, is; } friend ostream& operator<<(ostream& os, M x) { return os << x.v_; } friend bool operator==(M a, M b) { return a.v_ == b.v_; } friend bool operator!=(M a, M b) { return a.v_ != b.v_; } private: static pair<int, int> extgcd(int a, int b) { array<int, 2> x{1, 0}; while (b) swap(x[0] -= a / b * x[1], x[1]), swap(a %= b, b); return {x[0], a}; } uint32_t v_; }; using mint = LazyMontgomeryModInt<nttmod>; int main() { int n, q; cin >> n >> q; struct Node { mint sum, size; }; const Node id_node = {0, 0}; using Base = mint; auto make_node = [](const Base& c, int i) { return Node{c, 1}; }; auto combine = [](const Node& n1, const Node& n2) { return Node{n1.sum + n2.sum, n1.size + n2.size}; }; struct Update { mint a, b; }; const Update id_update = {1, 0}; auto apply_update = [](const Update& u, const Node& nd) { return Node{nd.sum * u.a + nd.size * u.b, nd.size}; }; auto compose_updates = [](const Update& u, const Update& v) { return Update{u.a * v.a, u.a * v.b + u.b}; }; vector<Base> a(n); for (auto& x : a) cin >> x; lazy_segtree seg(a, id_node, make_node, combine, id_update, apply_update, compose_updates); static_assert(decltype(seg)::is_lazy); while (q--) { int t, l, r; cin >> t >> l >> r; if (t == 1) { cout << seg.query(l, r).sum.get() << '\n'; } else { int a, b; cin >> a >> b; seg.update(l, r, Update{a, b}); } } }