#pragma GCC optimize("O3") #ifdef LOCAL #include "algo/debug_ver2.hpp" #else #define _debug(...) 42 #endif #include using namespace std; template struct LazySegmentTree { int n; vector nodes; vector lazy; vector sizes; T ti; U ui; function op; function mapping; function composition; int bit_width(int x) { int ret = 0; while (x) x >>= 1, ++ret; return ret; } LazySegmentTree(int size, T ti, U ui, function op, function mapping, function composition) : ti(ti), ui(ui), op(op), mapping(mapping), composition(composition) { n = 1; while (n < size) n *= 2; nodes.resize(n * 2, ti); lazy.resize(n * 2, ui); sizes.resize(n * 2); for (int i = 0; i < size; ++i) sizes[n + i] = 1; for (int i = n - 1; i > 0; --i) sizes[i] = sizes[i * 2] + sizes[i * 2 + 1]; } LazySegmentTree(vector vec, T ti, U ui, function op, function mapping, function composition) : LazySegmentTree(vec.size(), ti, ui, op, mapping, composition) { build(vec); } void build(vector vec) { for (int i = 0; i < n; ++i) nodes[n + i] = vec[i]; for (int i = n - 1; i > 0; --i) update(i); } void set(int k, T x) { k += n; for (int i = bit_width((unsigned int)n) - 1; i > 0; --i) propagate(k >> i); nodes[k] = x; for (int i = 1; i < bit_width((unsigned int)n); ++i) update(k >> i); } T get(int k) { k += n; for (int i = bit_width((unsigned int)n) - 1; i > 0; --i) propagate(k >> i); return nodes[k]; } T prod(int l, int r) { l += n, r += n; for (int i = bit_width((unsigned int)n) - 1; i > 0; --i) { if (((l >> i) << i) != l) propagate(l >> i); if (((r >> i) << i) != r) propagate((r - 1) >> i); } T l_cum = ti, r_cum = ti; for (; l < r; l /= 2, r /= 2) { if (l % 2 == 1) l_cum = op(l_cum, nodes[l++]); if (r % 2 == 1) r_cum = op(r_cum, nodes[--r]); } return op(l_cum, r_cum); } T all_prod() { return nodes[1]; } void apply(int k, U x) { k += n; for (int i = bit_width((unsigned int)n) - 1; i > 0; --i) propagate(k >> i); nodes[k] = mapping(nodes[k], x, sizes[k]); for (int i = 1; i < bit_width((unsigned int)n); ++i) update(k >> i); } void apply(int l, int r, U x) { l += n, r += n; for (int i = bit_width((unsigned int)n) - 1; i > 0; --i) { if (((l >> i) << i) != l) propagate(l >> i); if (((r >> i) << i) != r) propagate((r - 1) >> i); } for (int l2 = l, r2 = r; l2 < r2; l2 /= 2, r2 /= 2) { if (l2 % 2 == 1) all_apply(l2++, x); if (r2 % 2 == 1) all_apply(--r2, x); } for (int i = 1; i < bit_width((unsigned int)n); ++i) { if (((l >> i) << i) != l) update(l >> i); if (((r >> i) << i) != r) update((r - 1) >> i); } } private: void update(int x) { nodes[x] = op(nodes[x * 2], nodes[x * 2 + 1]); } void all_apply(int i, U x) { nodes[i] = mapping(nodes[i], x, sizes[i]); if (i < n) lazy[i] = composition(lazy[i], x); } void propagate(int i) { all_apply(i * 2, lazy[i]); all_apply(i * 2 + 1, lazy[i]); lazy[i] = ui; } }; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); int n, q; cin >> n >> q; LazySegmentTree, array> lsgt(n, {0, 0}, {-1, -1}, [](array x, array y) -> array { return {x[0] + y[0], x[1] + y[1]}; }, [](array x, array y, int len) -> array { return y == array{-1, -1} ? x : array{y[0] * len, y[1] * len}; }, [](array x, array y) -> array { return y == array{-1, -1} ? x : y; } ); array scores; for (int _ = 0; _ < q; ++_) { int x, l, r; cin >> x >> l >> r; ++r; if (x == 0) { array counts = lsgt.prod(l, r); if (counts[0] == counts[1]) continue; int tar = max_element(counts.begin(), counts.end()) - counts.begin(); scores[tar] += counts[tar]; } else lsgt.apply(l, r, {x == 1, x == 2}); } scores[0] += lsgt.all_prod()[0]; scores[1] += lsgt.all_prod()[1]; cout << scores[0] << ' ' << scores[1] << '\n'; }