#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include /* (=^o^=) */ #define int ll; // #define private public /* macro */ #define FOR(i, b, e) for(ll i = (ll)(b); i < (ll)(e); ++i) #define RFOR(i, b, e) for(ll i = (ll)(e-1); i >= (ll)(b); --i) #define REP(i, n) FOR(i, 0, n) #define RREP(i, n) RFOR(i, 0, n) #define REPC(x,c) for(const auto& x:(c)) #define REPI2(it,b,e) for(auto it = (b); it != (e); ++it) #define REPI(it,c) REPI2(it, (c).begin(), (c).end()) #define RREPI(it,c) REPI2(it, (c).rbegin(), (c).rend()) #define REPI_ERACE2(it, b, e) for(auto it = (b); it != (e);) #define REPI_ERACE(it, c) REPI_ERACE2(it, (c).begin(), (c).end()) #define ALL(x) (x).begin(),(x).end() #define cauto const auto& /* macro func */ #define SORT(x) do{sort(ALL(x));}while(false) #define RSORT(x) do{sort((x).rbegin(),(x).rend());}while(false) #define UNIQUE(v) do{v.erase( unique(v.begin(), v.end()), v.end() );}while(false) #define MAX(x,y) do{x = std::max(x,y);}while(false) #define MIN(x,y) do{x = std::min(x,y);}while(false) #define BR do{cout<<"\n";}while(false) #define dump(...) do{ auto __DUMP_NAME_LIST__ = split(#__VA_ARGS__,','); print(__DUMP_NAME_LIST__, __VA_ARGS__);BR;}while(false) /* type define */ using ll = long long; using PAIR = std::pair; using VS = std::vector; using VL = std::vector; using VVL = std::vector; using VVVL = std::vector; using VD = std::vector; /* using std */ using std::cout; constexpr char endl = '\n'; using std::cin; using std::sort; using std::pair; using std::string; using std::stack; using std::queue; using std::vector; using std::list; using std::map; using std::unordered_map; using std::multimap; using std::unordered_multimap; using std::set; using std::unordered_set; using std::unordered_multiset; using std::multiset; using std::bitset; using std::priority_queue; /* constant value */ constexpr ll MOD = 1000000007; //constexpr ll MOD = 998244353; /* Initial processing */ struct Preprocessing { Preprocessing() { std::cin.tie(0); std::ios::sync_with_stdio(0); }; }_Preprocessing; /* input output */ template std::istream& operator >> (std::istream& is, vector& vec) { for (T& x : vec) is >> x; return is; } templatestd::ostream& operator<<(std::ostream& os, const std::pair& p) { os << "(" << p.first << ", " << p.second << ")"; return os; } /* for dump function */ inline std::list split(std::string str, char del) { std::list sList; string s = ""; for (const auto& c : str) { if (c == del) { sList.emplace_back(s); s = ""; } else { if (c != ' ' || del == ' ') { s += c; } } }sList.emplace_back(s); return sList; } templatestruct has_begin { private: template static auto check(U x) -> decltype(x.begin(), std::true_type{}); static std::false_type check(...); public: static bool const value = decltype(check(std::declval()))::value; }; inline void print(std::list& str); template::value, std::nullptr_t> = nullptr>inline void print(std::list& str, const Primitive& x, const Tail&... tail); templateinline auto print(std::list& str, const Container& c, const Tail&... tail) -> decltype(c.begin()); templateinline void print(std::list& str, const std::string& s, const Tail&... tail); templateinline auto printSingle(const Container& c) ->decltype(c.begin()) { for (const auto& x : c) { std::cout << x << " "; }std::cout << "\n"; return c.begin(); } template::value, std::nullptr_t> = nullptr>inline void printSingle(const Primitive& x) { std::cout << x << " "; } inline void print(std::list& str) {} template::value, std::nullptr_t> = nullptr>inline void print(std::list& str, const Primitive& x, const Tail&... tail) { std::cout << *str.begin() << ":" << x << " "; if (sizeof...(tail) > 0) { std::cout << "\n"; str.pop_front(); print(str, tail...); } } templateinline auto print(std::list& str, const Container& c, const Tail&... tail) ->decltype(c.begin()) { std::cout << "-- " << *str.begin() << " --\n"; for (const auto& x : c) { printSingle(x); BR; }std::cout << "\n"; str.pop_front(); print(str, tail...); return c.begin(); } templateinline void print(std::list& str, const std::string& s, const Tail&... tail) { std::cout << *str.begin() << ":" << s << "\n"; str.pop_front(); print(str, tail...); } //============================================================================================= /** * 遅延セグメント木を構成する * 4methodの変更により調整 */ template class LazySegmentTree { private: const T initialValue = { 0,0 }; const T ignoreValue = { 0,0 }; const T lazyIgnoreValue = { 0,0 }; const ll m_size; std::vector m_node; std::vector m_lazy; ll calcSize(ll n) { ll size = 1; while (size < n) { size *= 2; } return size; } void spreadLazy(ll k) { if (k >= m_size - 1) { return; } m_lazy[2 * k + 1] = { m_lazy[k].first / 2,m_lazy[k].second / 2 }; m_lazy[2 * k + 2] = { m_lazy[k].first / 2,m_lazy[k].second / 2 }; } void reflectLazy(ll k) { m_node[k] = m_lazy[k]; } T merge(T xl, T xr) { return { xl.first + xr.first,xl.second + xr.second }; } T rangeUpdate(T x, ll l, ll r) { return { x.first * (r - l) ,x.second*(r - l) }; } public: LazySegmentTree() = delete; LazySegmentTree(ll n) : m_size(calcSize(n)), m_node(m_size * 2 - 1, initialValue), m_lazy(m_size * 2 - 1, lazyIgnoreValue) { } void add(ll a, ll b, T x) { add(a, b + 1, x, 0, 0, m_size); /** cout << "-- tree -- " << endl; REP(i, 2 * m_size - 1) { cout << m_node[i] << " " << m_lazy[i] << endl; } /*//**/ } void add(ll a, ll b, T x, ll k, ll l, ll r) { eval(k); if (r <= a || b <= l) { return; } if (a <= l && r <= b) { m_lazy[k] = rangeUpdate(x, l, r); eval(k); return; } add(a, b, x, 2 * k + 1, l, (l + r) / 2); add(a, b, x, 2 * k + 2, (l + r) / 2, r); m_node[k] = merge(m_node[2 * k + 1], m_node[2 * k + 2]); } void eval(ll k) { if (m_lazy[k] == lazyIgnoreValue) { return; } reflectLazy(k); spreadLazy(k); m_lazy[k] = lazyIgnoreValue; } T query(ll a, ll b) { return query(a, b + 1, 0, 0, m_size); } T query(ll a, ll b, ll k, ll l, ll r) { if (r <= a || b <= l) { return ignoreValue; } eval(k); if (a <= l && r <= b) { return m_node[k]; } return merge( query(a, b, 2 * k + 1, l, (l + r) / 2), query(a, b, 2 * k + 2, (l + r) / 2, r) ); } }; signed main() { ll n, q; cin >> n >> q; auto tree = LazySegmentTree(n); ll sa = 0, sb = 0; REP(_, q) { ll k, l, r; cin >> k >> l >> r; if (k > 0) { tree.add(l, r, { k == 1,k == 2 }); } else { auto p = tree.query(l, r); if (p.first > p.second) { sa += p.first; } else if (p.first < p.second) { sb += p.second; } } } auto p = tree.query(0, n - 1); sa += p.first; sb += p.second; cout << sa << " " << sb << endl; }