#include #include namespace copr { namespace seg_util { constexpr int nextpow2(int x, int r = 1) { return r < x ? nextpow2(x, r + r) : r; } } // namespace seg_util template struct LazySegTree { using data_type = typename Monoid::value_type; using lazy_type = typename Lazy::value_type; const int N; const data_type empty = Monoid::empty(); const lazy_type nil = Lazy::empty(); std::vector data; std::vector lazy; LazySegTree(int size) : N(seg_util::nextpow2(size)) { data.assign(N * 2, empty); lazy.assign(N * 2, nil); } inline void propagate(int x, int l, int r) { if (lazy[x] == nil) return; data[x] = Lazy::eval(data[x], lazy[x], l, r); if (x < N - 1) { lazy[x + x + 1] = Lazy::append(lazy[x + x + 1], lazy[x]); lazy[x + x + 2] = Lazy::append(lazy[x + x + 2], lazy[x]); } lazy[x] = nil; } void query(lazy_type v, int a, int b) { query(v, a, b, 0, 0, N); } void query(lazy_type v, int a, int b, int x, int l, int r) { propagate(x, l, r); if (r <= a || b <= l) return; if (a <= l && r <= b) { lazy[x] = Lazy::append(lazy[x], v); propagate(x, l, r); return; } int m = (l + r) / 2; query(v, a, b, x + x + 1, l, m); query(v, a, b, x + x + 2, m, r); data[x] = Monoid::append(data[x + x + 1], data[x + x + 2]); } data_type concat(int a, int b) { return concat(a, b, 0, 0, N); } data_type concat(int a, int b, int x, int l, int r) { propagate(x, l, r); if (r <= a || b <= l) return empty; if (a <= l && r <= b) return data[x]; int m = (l + r) / 2; return Monoid::append(concat(a, b, x + x + 1, l, m), concat(a, b, x + x + 2, m, r)); } }; } // namespace copr using namespace std; struct Sum { using value_type = int; static value_type append(value_type x, value_type y) { return x + y; } static value_type empty() { return 0; } struct FillQuery { using value_type = int; static value_type append(value_type x, value_type y) { return y; } static value_type empty() { return -1; } template static T eval(T v, value_type x, int l, int r) { return (r - l) * x; } }; }; using ll = long long; int main() { int N, Q; cin >> N >> Q; copr::LazySegTree A{N}, B{N}; ll a = 0, b = 0; for (int q = 0; q < Q; q++) { int x, l, r; cin >> x >> l >> r; r++; if (x == 0) { auto ac = A.concat(l, r); auto bc = B.concat(l, r); if (ac == bc) continue; if (ac < bc) { b += bc; } else { a += ac; } } else { A.query(x == 1, l, r); B.query(x == 2, l, r); } } a += A.concat(0, N); b += B.concat(0, N); cout << a << ' ' << b << endl; }