#include #include using namespace std; #define repeat(i, x) for (int i = 0; (i) < (x); (i)++) using int64 = long long; struct Element { using T = int; static inline constexpr T identity() { return 0; } static inline T op(const T& a, const T& b) { return a + b; } }; template struct Operation { using T = typename Object::T; using M = T; static inline constexpr M identity() { return -1; } static inline M op(const M& a, const M& b) { return (b == identity()) ? a : b; } // mpをaに適用する static inline T apply(const M& mp, const int a, int w) { return (mp == identity()) ? a : w * T(mp); } }; template class LazyPropagationSegmentTree { const int N; const int h; using T = typename Object::T; using M = typename Operator::M; std::vector t; std::vector lazy; inline int lowest_pow_of_2(int n) { int res = 1; while (res < n) res <<= 1; return res; } // log2_X <= nを満たす最大のXを計算 inline int log2(int n) { int res = 0; while (n >> (res + 1)) res++; return res; } inline void prop_to(int i) { t[i] = Object::op(t[2 * i], t[2 * i + 1]); } inline void eval(int i, int w) { if (i < N and lazy[i] != Operator::identity()) { t[i] = Operator::apply(lazy[i], t[i], w); if (2 * i < N) { // 伝搬 lazy[2 * i] = Operator::op(lazy[2 * i], lazy[i]); lazy[2 * i + 1] = Operator::op(lazy[2 * i + 1], lazy[i]); } else if (i < N) { t[2 * i] = Operator::apply(lazy[i], t[2 * i], w / 2); t[2 * i + 1] = Operator::apply(lazy[i], t[2 * i + 1], w / 2); } lazy[i] = Operator::identity(); } } public: LazyPropagationSegmentTree(int n) : N(lowest_pow_of_2(n)), h(log2(N) + 1), t(2 * N, Object::identity()), lazy(N, Operator::identity()) { } template LazyPropagationSegmentTree(InputIt first, InputIt last) : N(lowest_pow_of_2(std::distance(first, last))), h(log2(N) + 1), t(2 * N, Object::identity()), lazy(N, Operator::identity()) { std::copy(first, last, t + N); for (int i = N - 1; i > 0; i--) prop_to(i); } inline void update(int l, int r, M mp) { update(l, r, mp, 1, 0, N); } inline void update(int l, int r, M mp, int id, int nodel, int noder) { // 範囲外 eval(id, noder - nodel); // 演算の順序を守るためさきに伝播させる if (noder <= l or r <= nodel) return; if (id >= N) { // 葉 t[id] = Operator::apply(mp, t[id], 1); return; } if (l <= nodel and noder <= r) { lazy[id] = Operator::op(lazy[id], mp); eval(id, noder - nodel); } else { update(l, r, mp, 2 * id, nodel, (nodel + noder) / 2); update(l, r, mp, 2 * id + 1, (nodel + noder) / 2, noder); t[id] = Object::op(t[2 * id], t[2 * id + 1]); } } T get(int i) { i += N; for (int j = (h - 1); j > 0; j--) eval(i >> j, 1 << j); return t[i]; } T query(int l, int r) { return query(l, r, 1, 0, N); } T query(int l, int r, int id, int nodel, int noder) { // 範囲外 eval(id, noder - nodel); if (noder <= l or r <= nodel) return Object::identity(); // 完全に含まれる if (l <= nodel and noder <= r) return t[id]; T resl = query(l, r, 2 * id, nodel, (nodel + noder) / 2); T resr = query(l, r, 2 * id + 1, (nodel + noder) / 2, noder); return Object::op(resl, resr); } }; int main() { cin.tie(0); ios::sync_with_stdio(false); int N; cin >> N; static LazyPropagationSegmentTree> A(N), B(N); int Q; cin >> Q; int64 a_score = 0, b_score = 0; repeat (i, Q) { int x, l, r; cin >> x >> l >> r; r++; if (x == 0) { // ボーナスチャンス int a_cnt = A.query(l, r), b_cnt = B.query(l, r); if (a_cnt > b_cnt) a_score += a_cnt; else if (a_cnt < b_cnt) b_score += b_cnt; } else if (x == 1) { A.update(l, r, 1); B.update(l, r, 0); } else { A.update(l, r, 0); B.update(l, r, 1); } } a_score += A.query(0, N); b_score += B.query(0, N); cout << a_score << " " << b_score << endl; cerr << endl; return 0; }