Problems Submissions
Register Login 質問(Gitter) GitHub

Submit Info #3664

Problem Lang User Status Time Memory
Range Affine Range Sum cpp m2048so3 AC 1582 ms 54.89 MiB

ケース詳細
Name Status Time Memory
example_00 AC 28 ms 33.75 MiB
max_random_00 AC 1564 ms 54.85 MiB
max_random_01 AC 1576 ms 54.85 MiB
max_random_02 AC 1582 ms 54.89 MiB
random_00 AC 1258 ms 51.02 MiB
random_01 AC 1318 ms 51.10 MiB
random_02 AC 721 ms 49.82 MiB
small_00 AC 30 ms 33.68 MiB
small_01 AC 30 ms 33.71 MiB
small_02 AC 31 ms 33.73 MiB
small_03 AC 29 ms 33.75 MiB
small_04 AC 30 ms 33.67 MiB
small_05 AC 30 ms 33.75 MiB
small_06 AC 30 ms 33.75 MiB
small_07 AC 30 ms 33.75 MiB
small_08 AC 30 ms 33.71 MiB
small_09 AC 32 ms 33.75 MiB
small_random_00 AC 31 ms 33.75 MiB
small_random_01 AC 31 ms 33.75 MiB

#define NDEBUG #include <unordered_map> #include <functional> #include <algorithm> #include <iostream> #include <cassert> #include <cstring> #include <iomanip> #include <numeric> #include <utility> #include <random> #include <string> #include <vector> #include <cmath> #include <stack> #include <queue> #include <tuple> #include <set> #include <map> // [0, max) #define FOR0(var, max) for (sl (var) = 0; (var) < (max); ++(var)) // [min, max) #define FORi(var, min, max) for (sl (var) = (min); (var) < (max); ++(var)) // [min, max) #define FORi_INV(var, min, max) for (sl (var) = (max) - 1; (var) + 1 > (min); --(var)) #define FORITER(var, iter) for (auto (iter) = (var).begin(); (iter) != (var).end(); (iter)++) #define FORITER_INV(var, iter) for (auto (iter) = (var).rbegin(); (iter) != (var).rend(); (iter)++) // a < b < c #define LTLT(a, b, c) (((a) < (b)) && ((b) < (c))) // a <= b < c #define LELT(a, b, c) (((a) <= (b)) && ((b) < (c))) // a < b <= c #define LTLE(a, b, c) (((a) < (b)) && ((b) <= (c))) // a <= b <= c #define LELE(a, b, c) (((a) <= (b)) && ((b) <= (c))) #ifndef NDEBUG # define MASSERT(cond) m_assert(cond, __LINE__, #cond); #else # define MASSERT(...) #endif using namespace std; using uc = unsigned char; using ui = unsigned int; using ul = unsigned long long int; using ull = __uint128_t; using sc = signed char; using si = signed int; using sl = signed long long int; using sll = __int128_t; using ld = long double; void m_assert(const bool& cond, const sl& line, const char *condstr) { if (!cond) { cerr << "Assertion Failed: " << condstr << " at line " << line << endl; exit(1); } } namespace std { template <> struct is_integral<__int128_t> { constexpr static bool value = true; }; }; /* (identity element, operation) */ template <class T> struct Monoid { const T identity; const function<T(T, T)> op; Monoid (const T& _ident, const function<T(T, T)>& _op) : identity(_ident), op(_op) {}; }; /* f: T * E -> T */ template <class T, class E> using MonoidAction = function<T(T, E)>; template <class T, class E, sl K> class LazyPropagationSegmentTree { const Monoid<T> monoid; const Monoid<E> operator_monoid; const MonoidAction<T, E> action; const sl N = (1 << K); T tree[2 * (1 << K) - 1]; E lazytree[2 * (1 << K) - 1]; inline si parent(si i) { MASSERT(LELT(0, i, 2 * N - 1)); MASSERT(i != 0); return (i - 1) / 2; } inline si left(si i) { MASSERT(LELT(0, i, 2 * N - 1)); return i * 2 + 1; } inline si right(si i) { MASSERT(LELT(0, i, 2 * N - 1)); return i * 2 + 2; } inline si leaf(si i) { MASSERT(LELT(0, i, N)); return i + N - 1; } inline bool is_leaf(si i) { MASSERT(LELT(0, i, 2 * N - 1)); return (N - 1 <= i); } inline void propagate(si idx) { MASSERT(LELT(0, idx, 2 * N - 1)); if (lazytree[idx] == operator_monoid.identity) { return; } if (!is_leaf(idx)) { lazytree[left(idx)] = operator_monoid.op(lazytree[left(idx)], lazytree[idx]); lazytree[right(idx)] = operator_monoid.op(lazytree[right(idx)], lazytree[idx]); } tree[idx] = action(tree[idx], lazytree[idx]); lazytree[idx] = operator_monoid.identity; } T apply_impl(si a, si b, E x, si idx, si l, si r) { MASSERT(LELT(0, l, r) && r <= (2 * N - 1)); MASSERT(LELT(0, a, b) && b <= (2 * N - 1)); MASSERT(LELT(0, idx, 2 * N - 1)); propagate(idx); if (r <= a || b <= l) { return tree[idx]; } if (a <= l && r <= b) { // [l, r) covered by [a, b) lazytree[idx] = x; return action(tree[idx], lazytree[idx]); } else { si t = (l + r) / 2; T vL = apply_impl(a, b, x, left(idx), l, t); T vR = apply_impl(a, b, x, right(idx), t, r); tree[idx] = monoid.op(vL, vR); return tree[idx]; } } T query_impl(si a, si b, si idx, si l, si r) { MASSERT(LELT(0, l, r) && r <= (2 * N - 1)); MASSERT(LELT(0, a, b) && b <= (2 * N - 1)); MASSERT(LELT(0, idx, 2 * N - 1)); propagate(idx); if (r <= a || b <= l) { return monoid.identity; } if (a <= l && r <= b) { // [l, r) covered by [a, b) return tree[idx]; } else { si t = (l + r) / 2; T vL = query_impl(a, b, left(idx), l, t); T vR = query_impl(a, b, right(idx), t, r); return monoid.op(vL, vR); } } public: LazyPropagationSegmentTree(const Monoid<T>& _monoid, const Monoid<E>& _operator, const MonoidAction<T, E>& _action, const T& default_value) : monoid(_monoid), operator_monoid(_operator), action(_action) { queue<si> Q; FOR0(i, N) { tree[leaf(i)] = default_value; if ((i & 1) == 0) { Q.push(parent(leaf(i))); } } while (!Q.empty()) { auto v = Q.front(); Q.pop(); tree[v] = monoid.op(tree[left(v)], tree[right(v)]); if (v != 0) { if (left(parent(v)) == v) { Q.push(parent(v)); } } } FOR0(i, 2 * N - 1) { lazytree[i] = operator_monoid.identity; } } LazyPropagationSegmentTree(const Monoid<T>& _monoid, const Monoid<E>& _operator, const MonoidAction<T, E>& _action) : LazyPropagationSegmentTree(_monoid, _operator, _action, _monoid.identity) { } /* operate x to [a, b) */ void apply(si a, si b, E x) { MASSERT(LELT(0, a, b) && b <= (2 * N - 1)); apply_impl(a, b, x, 0, 0, N); } // [a, b) T query(si a, si b) { MASSERT(LELT(0, a, b) && b <= (2 * N - 1)); return query_impl(a, b, 0, 0, N); } }; static sl N, Q; static vector<tuple<si, sl, sl, sl, sl>> Qi; const static sl MOD = 998244353LL; using LinearFunction = pair<sl, sl>; static Monoid<pair<sl, sl>> monoid ({0, 1}, [](pair<sl, sl> a, pair<sl, sl> b) -> pair<sl, sl> { return { (a.first + b.first) % MOD, (a.second + b.second) % MOD }; }); static MonoidAction<pair<sl, sl>, LinearFunction> action = [](pair<sl, sl> a, LinearFunction f) -> pair<sl, sl> { return { ((f.first * a.first) % MOD + (f.second * a.second) % MOD) % MOD, a.second }; }; static Monoid<LinearFunction> operator_monoid ({1, 0}, [](const LinearFunction& f, const LinearFunction& g) -> LinearFunction { return { (g.first * f.first) % MOD, ((g.first * f.second) % MOD + g.second) % MOD }; }); LazyPropagationSegmentTree<pair<sl, sl>, pair<sl, sl>, 19> tree (monoid, operator_monoid, action); void solve(void) { FOR0(i, Q) { sl l = get<1>(Qi[i]); sl r = get<2>(Qi[i]); sl b = get<3>(Qi[i]); sl c = get<4>(Qi[i]); if (get<0>(Qi[i]) == 0) { tree.apply(l, r, {b, c}); } else { printf("%lld\n", tree.query(l, r).first); } } } int main(void) { scanf("%lld %lld", &N, &Q); sl t; FOR0(i, N) { scanf("%lld", &t); tree.apply(i, i + 1, {0, t}); } Qi.resize(Q); FOR0(i, Q) { scanf("%d %lld %lld", &get<0>(Qi[i]), &get<1>(Qi[i]), &get<2>(Qi[i])); if (get<0>(Qi[i]) == 0) { scanf("%lld %lld", &get<3>(Qi[i]), &get<4>(Qi[i])); } } solve(); return 0; }