This documentation is automatically generated by online-judge-tools/verification-helper
View the Project on GitHub toyama1710/cpp_library
#define PROBLEM \ "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_I" #include <iostream> #include <utility> #include "../../segment_tree/lazy_segment_tree.hpp" using namespace std; using llong = long long; struct Monoid { using T = pair<llong, llong>; using value_type = pair<llong, llong>; inline static T identity() { return {0ll, 0ll}; }; inline static T operation(T &a, T &b) { return {a.first + b.first, a.second + b.second}; }; }; struct Operator { using E = llong; using value_type = llong; inline static E identity() { return -1024; }; inline static E operation(E &a, E &b) { if (b == identity()) return a; else return b; }; }; struct A { using value_structure = Monoid; using operator_structure = Operator; using T = typename value_structure::T; using E = typename operator_structure::E; inline static T operation(T &a, E &b) { if (b == operator_structure::identity()) return a; return {b * a.second, a.second}; }; }; llong n, q; llong com, s, t, x; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); cin >> n >> q; LazySegmentTree<A> seg(n); for (int i = 0; i < n; i++) seg.set(i, {0ll, 1ll}); while (q--) { cin >> com; if (com == 0) { cin >> s >> t >> x; seg.update(s, t + 1, x); } else { cin >> s >> t; cout << seg.fold(s, t + 1).first << '\n'; } } }
#line 1 "test/aoj/DSL2I.test.cpp" #define PROBLEM \ "http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=DSL_2_I" #include <iostream> #include <utility> #line 1 "segment_tree/lazy_segment_tree.hpp" #include <cstdint> #include <vector> #line 1 "bit/ctz.hpp" #line 5 "bit/ctz.hpp" inline int ctz32_(uint32_t bit) { static const int table[] = { 0, 1, 2, 6, 3, 11, 7, 16, 4, 14, 12, 21, 8, 23, 17, 26, 31, 5, 10, 15, 13, 20, 22, 25, 30, 9, 19, 24, 29, 18, 28, 27, }; static const uint32_t de_bruijn = 0x04653adf; bit &= ~bit + 1; return table[(bit * de_bruijn) >> 27]; }; inline int ctz32(uint32_t bit) { if (bit == 0) return 32; #ifdef __has_builtin return __builtin_ctz(bit); #else return ctz32_(bit); #endif }; inline int ctz64_(uint64_t bit) { static const int table[] = { 0, 1, 2, 7, 3, 13, 8, 19, 4, 25, 14, 28, 9, 34, 20, 40, 5, 17, 26, 38, 15, 46, 29, 48, 10, 31, 35, 54, 21, 50, 41, 57, 63, 6, 12, 18, 24, 27, 33, 39, 16, 37, 45, 47, 30, 53, 49, 56, 62, 11, 23, 32, 36, 44, 52, 55, 61, 22, 43, 51, 60, 42, 59, 58, }; static const uint64_t de_bruijn = 0x0218a392cd3d5dbfull; bit &= ~bit + 1; return table[(bit * de_bruijn) >> 58]; }; inline int ctz64(uint64_t bit) { if (bit == 0) return 64; #ifdef __has_builtin return __builtin_ctzll(bit); #else return ctz64_(bit); #endif }; #line 1 "bit/msb.hpp" #line 5 "bit/msb.hpp" inline uint32_t msb32_(uint32_t bit) { bit |= bit >> 1; bit |= bit >> 2; bit |= bit >> 4; bit |= bit >> 8; bit |= bit >> 16; return bit ^ (bit >> 1); }; inline uint32_t msb32(uint32_t x) { if (x == 0) return 0; #ifdef __has_builtin return 1u << (31 - __builtin_clz(x)); #else return msb32_(x); #endif }; inline uint64_t msb64_(uint64_t bit) { bit |= bit >> 1; bit |= bit >> 2; bit |= bit >> 4; bit |= bit >> 8; bit |= bit >> 16; bit |= bit >> 32; return bit ^ (bit >> 1); }; inline uint64_t msb64(uint64_t x) { if (x == 0) return 0; #ifdef __has_builtin return 1ull << (63 - __builtin_clzll(x)); #else return msb64_(x); #endif }; #line 9 "segment_tree/lazy_segment_tree.hpp" //=== template <class MonoidwithOperator> struct LazySegmentTree { using M = MonoidwithOperator; using V = typename M::value_structure; using T = typename V::value_type; using O = typename M::operator_structure; using E = typename O::value_type; // T + T V::operation // E + E O::operation // T + E -> T M::operation struct Node { T dat; E lazy; Node(T dat, E lazy) : dat(dat), lazy(lazy){}; }; std::vector<Node> tree; LazySegmentTree() = default; explicit LazySegmentTree(uint32_t n) : tree(n * 2 + 2, Node(V::identity(), O::identity())){}; int size() { return tree.size() >> 1; }; void propagation(uint32_t k) { const uint32_t l = (k << 1) | 0; const uint32_t r = (k << 1) | 1; tree[l].lazy = O::operation(tree[l].lazy, tree[k].lazy); tree[r].lazy = O::operation(tree[r].lazy, tree[k].lazy); tree[l].dat = M::operation(tree[l].dat, tree[k].lazy); tree[r].dat = M::operation(tree[r].dat, tree[k].lazy); tree[k].lazy = O::identity(); }; void push_down(uint32_t k) { if (k == 0) return; uint32_t w = ctz32(msb32(k)); for (int i = w; i > 0; i--) propagation(k >> i); }; void recalc(uint32_t k) { while (k > 1) { k >>= 1; tree[k].dat = V::operation(tree[(k << 1) | 0].dat, tree[(k << 1) | 1].dat); } }; // [l, r) += op void update(uint32_t l, uint32_t r, E op) { l += size(); r += size(); uint32_t tmpl = l; uint32_t tmpr = r; push_down(l); push_down(r - 1); while (l < r) { if (l & 1) { tree[l].lazy = O::operation(tree[l].lazy, op); tree[l].dat = M::operation(tree[l].dat, op); l++; } if (r & 1) { --r; tree[r].lazy = O::operation(tree[r].lazy, op); tree[r].dat = M::operation(tree[r].dat, op); } l >>= 1; r >>= 1; } push_down(tmpl); push_down(tmpr - 1); recalc(tmpl); recalc(tmpr - 1); }; void update(uint32_t idx, T x) { idx += size(); push_down(idx); tree[idx].dat = x; recalc(idx); }; void set(uint32_t idx, T x) { update(idx, x); }; // foldl[l, r) T fold(uint32_t l, uint32_t r) { l += size(); r += size(); push_down(l); push_down(r - 1); T lv = V::identity(); T rv = V::identity(); while (l < r) { if (l & 1) lv = V::operation(lv, tree[l].dat), l++; if (r & 1) --r, rv = V::operation(tree[r].dat, rv); l >>= 1; r >>= 1; } return V::operation(lv, rv); }; T operator[](const uint32_t &k) { push_down(k + size()); return tree[k + size()].dat; }; }; //=== #line 7 "test/aoj/DSL2I.test.cpp" using namespace std; using llong = long long; struct Monoid { using T = pair<llong, llong>; using value_type = pair<llong, llong>; inline static T identity() { return {0ll, 0ll}; }; inline static T operation(T &a, T &b) { return {a.first + b.first, a.second + b.second}; }; }; struct Operator { using E = llong; using value_type = llong; inline static E identity() { return -1024; }; inline static E operation(E &a, E &b) { if (b == identity()) return a; else return b; }; }; struct A { using value_structure = Monoid; using operator_structure = Operator; using T = typename value_structure::T; using E = typename operator_structure::E; inline static T operation(T &a, E &b) { if (b == operator_structure::identity()) return a; return {b * a.second, a.second}; }; }; llong n, q; llong com, s, t, x; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); cin >> n >> q; LazySegmentTree<A> seg(n); for (int i = 0; i < n; i++) seg.set(i, {0ll, 1ll}); while (q--) { cin >> com; if (com == 0) { cin >> s >> t >> x; seg.update(s, t + 1, x); } else { cin >> s >> t; cout << seg.fold(s, t + 1).first << '\n'; } } }