This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub knshnb/competitive_library
#define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/2/DSL_2_G" #include <bits/stdc++.h> // clang-format off using Int = long long; #define REP_(i, a_, b_, a, b, ...) for (Int i = (a), lim##i = (b); i < lim##i; i++) #define REP(i, ...) REP_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__) #define ALL(v) std::begin(v), std::end(v) struct SetupIO { SetupIO() { std::cin.tie(nullptr), std::ios::sync_with_stdio(false), std::cout << std::fixed << std::setprecision(13); } } setup_io; #ifndef dump #define dump(...) #endif // clang-format on /** * author: knshnb * created: Wed Sep 30 01:45:16 JST 2020 **/ #define CALL_FROM_TEST #include "../../src/DataStructure/LazySegmentTreeACL.hpp" #undef CALL_FROM_TEST signed main() { int n, Q; std::cin >> n >> Q; sum_add::segtree seg(std::vector<sum_add::S>(n, {0, 1})); REP(q, Q) { int c, s, t; std::cin >> c >> s >> t, s--; if (c == 0) { int x; std::cin >> x; seg.apply(s, t, x); } else { std::cout << seg.prod(s, t).sum << "\n"; } } }
#line 1 "test/aoj/DSL_2_G.test.cpp" #define PROBLEM "https://onlinejudge.u-aizu.ac.jp/courses/library/3/DSL/2/DSL_2_G" #include <bits/stdc++.h> // clang-format off using Int = long long; #define REP_(i, a_, b_, a, b, ...) for (Int i = (a), lim##i = (b); i < lim##i; i++) #define REP(i, ...) REP_(i, __VA_ARGS__, __VA_ARGS__, 0, __VA_ARGS__) #define ALL(v) std::begin(v), std::end(v) struct SetupIO { SetupIO() { std::cin.tie(nullptr), std::ios::sync_with_stdio(false), std::cout << std::fixed << std::setprecision(13); } } setup_io; #ifndef dump #define dump(...) #endif // clang-format on /** * author: knshnb * created: Wed Sep 30 01:45:16 JST 2020 **/ #define CALL_FROM_TEST #line 2 "src/DataStructure/LazySegmentTreeACL.hpp" #ifdef _MSC_VER #include <intrin.h> #endif namespace atcoder { namespace internal { // @param n `0 <= n` // @return minimum non-negative `x` s.t. `n <= 2**x` int ceil_pow2(int n) { int x = 0; while ((1U << x) < (unsigned int)(n)) x++; return x; } // @param n `1 <= n` // @return minimum non-negative `x` s.t. `(n & (1 << x)) != 0` int bsf(unsigned int n) { #ifdef _MSC_VER unsigned long index; _BitScanForward(&index, n); return index; #else return __builtin_ctz(n); #endif } } // namespace internal } // namespace atcoder #line 38 "src/DataStructure/LazySegmentTreeACL.hpp" namespace atcoder { template <class S, S (*op)(S, S), S (*e)(), class F, S (*mapping)(F, S), F (*composition)(F, F), F (*id)()> struct lazy_segtree { public: lazy_segtree() : lazy_segtree(0) {} lazy_segtree(int n) : lazy_segtree(std::vector<S>(n, e())) {} lazy_segtree(const std::vector<S>& v) : _n(int(v.size())) { log = internal::ceil_pow2(_n); size = 1 << log; d = std::vector<S>(2 * size, e()); lz = std::vector<F>(size, id()); for (int i = 0; i < _n; i++) d[size + i] = v[i]; for (int i = size - 1; i >= 1; i--) { update(i); } } void set(int p, S x) { assert(0 <= p && p < _n); p += size; for (int i = log; i >= 1; i--) push(p >> i); d[p] = x; for (int i = 1; i <= log; i++) update(p >> i); } S get(int p) { assert(0 <= p && p < _n); p += size; for (int i = log; i >= 1; i--) push(p >> i); return d[p]; } S prod(int l, int r) { assert(0 <= l && l <= r && r <= _n); if (l == r) return e(); l += size; r += size; for (int i = log; i >= 1; i--) { if (((l >> i) << i) != l) push(l >> i); if (((r >> i) << i) != r) push(r >> i); } S sml = e(), smr = e(); while (l < r) { if (l & 1) sml = op(sml, d[l++]); if (r & 1) smr = op(d[--r], smr); l >>= 1; r >>= 1; } return op(sml, smr); } S all_prod() { return d[1]; } void apply(int p, F f) { assert(0 <= p && p < _n); p += size; for (int i = log; i >= 1; i--) push(p >> i); d[p] = mapping(f, d[p]); for (int i = 1; i <= log; i++) update(p >> i); } void apply(int l, int r, F f) { assert(0 <= l && l <= r && r <= _n); if (l == r) return; l += size; r += size; for (int i = log; i >= 1; i--) { if (((l >> i) << i) != l) push(l >> i); if (((r >> i) << i) != r) push((r - 1) >> i); } { 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 = 1; i <= log; i++) { if (((l >> i) << i) != l) update(l >> i); if (((r >> i) << i) != r) update((r - 1) >> i); } } template <bool (*g)(S)> int max_right(int l) { return max_right(l, [](S x) { return g(x); }); } template <class G> int max_right(int l, G g) { assert(0 <= l && l <= _n); assert(g(e())); if (l == _n) return _n; l += size; for (int i = log; i >= 1; i--) push(l >> i); S sm = e(); do { while (l % 2 == 0) l >>= 1; if (!g(op(sm, d[l]))) { while (l < size) { push(l); l = (2 * l); if (g(op(sm, d[l]))) { sm = op(sm, d[l]); l++; } } return l - size; } sm = op(sm, d[l]); l++; } while ((l & -l) != l); return _n; } template <bool (*g)(S)> int min_left(int r) { return min_left(r, [](S x) { return g(x); }); } template <class G> int min_left(int r, G g) { assert(0 <= r && r <= _n); assert(g(e())); if (r == 0) return 0; r += size; for (int i = log; i >= 1; i--) push((r - 1) >> i); S sm = e(); do { r--; while (r > 1 && (r % 2)) r >>= 1; if (!g(op(d[r], sm))) { while (r < size) { push(r); r = (2 * r + 1); if (g(op(d[r], sm))) { sm = op(d[r], sm); r--; } } return r + 1 - size; } sm = op(d[r], sm); } while ((r & -r) != r); return 0; } private: int _n, size, log; std::vector<S> d; std::vector<F> lz; void update(int k) { d[k] = op(d[2 * k], d[2 * k + 1]); } void all_apply(int k, F f) { d[k] = mapping(f, d[k]); if (k < size) lz[k] = composition(f, lz[k]); } void push(int k) { all_apply(2 * k, lz[k]); all_apply(2 * k + 1, lz[k]); lz[k] = id(); } }; } // namespace atcoder namespace min_update { using T = Int; using S = T; S op(S x, S y) { return std::min<S>(x, y); } S e() { return std::numeric_limits<S>::max(); } using F = T; constexpr F dummy = std::numeric_limits<F>::min(); S mapping(F f, S x) { return f == dummy ? x : f; } F composition(F f, F g) { return f == dummy ? g : f; } F id() { return dummy; } using segtree = atcoder::lazy_segtree<S, op, e, F, mapping, composition, id>; }; // namespace min_update namespace sum_add { using T = Int; struct S { T sum; int len; }; S op(S x, S y) { return {x.sum + y.sum, x.len + y.len}; } S e() { return {0, 0}; } using F = T; S mapping(F f, S x) { return {x.sum + f * x.len, x.len}; } F composition(F f, F g) { return f + g; } F id() { return 0; } using segtree = atcoder::lazy_segtree<S, op, e, F, mapping, composition, id>; } // namespace sum_add namespace min_add { using T = Int; using S = T; S op(S x, S y) { return std::min(x, y); } S e() { return std::numeric_limits<S>::max() / 2; } using F = T; S mapping(F f, S x) { return x + f; } F composition(F f, F g) { return f + g; } F id() { return 0; } using segtree = atcoder::lazy_segtree<S, op, e, F, mapping, composition, id>; } // namespace min_add namespace sum_update { using T = Int; struct S { T sum; int len; }; S op(S x, S y) { return {x.sum + y.sum, x.len + y.len}; } S e() { return {0, 0}; } using F = T; constexpr F dummy = std::numeric_limits<F>::min(); S mapping(F f, S x) { return f == dummy ? x : S{f * x.len, x.len}; } F composition(F f, F g) { return f == dummy ? g : f; } F id() { return dummy; } using segtree = atcoder::lazy_segtree<S, op, e, F, mapping, composition, id>; } // namespace sum_update #line 20 "test/aoj/DSL_2_G.test.cpp" #undef CALL_FROM_TEST signed main() { int n, Q; std::cin >> n >> Q; sum_add::segtree seg(std::vector<sum_add::S>(n, {0, 1})); REP(q, Q) { int c, s, t; std::cin >> c >> s >> t, s--; if (c == 0) { int x; std::cin >> x; seg.apply(s, t, x); } else { std::cout << seg.prod(s, t).sum << "\n"; } } }