// // 2017/Oct/03. // Yukicoder No.255 Splarrraaay // ****************************************************************** // Segment Tree with Lazy Propagation // Add and Assignment modification on range, // Queries for weighted sum on range, // with coordinate compression // ****************************************************************** #include using namespace std; constexpr long long mod = 1e18+9; template struct LazyData{ T add; T assign; bool has_assign; LazyData(T v = 0, T w = 0, bool tf = false): add(v), assign(w), has_assign(tf) {} }; template class SegTree{ size_t n; int h; vector data; // data[i]: 区間i の重みづけ合計 vector weight; // weight[i]: 区間i の重み vector> lazy; // lazy[i]: 区間i の未伝搬の遅延評価データ static T combine(T L, T R){ return L + R; } void apply(size_t i, T v, int command_type){ if (command_type == 0){ apply_assign(i, v); }else{ apply_add(i, v); } } void apply_assign(size_t i, T v) { // v: value to assign data[i] = weight[i] * v; if (i < n) { lazy[i].add = 0; lazy[i].assign = v; lazy[i].has_assign = true; } } void apply_add(size_t i, T v) { data[i] += weight[i] * v; if (i < n) (lazy[i].has_assign ? lazy[i].assign : lazy[i].add) += v; } void build(size_t i){ // update all the parents of node i. while (i >>= 1) if (not lazy[i].has_assign) data[i] = combine(data[i*2], data[i*2+1]) + lazy[i].add * weight[i]; } void push(size_t p){ // propagates the changes from the root to node p. for (int s = h; s > 0; --s){ size_t i = p >> s; if (lazy[i].has_assign){ apply_assign(i*2, lazy[i].assign); apply_assign(i*2+1, lazy[i].assign); lazy[i].has_assign = false; }else if (lazy[i].add != 0){ apply_add(i*2, lazy[i].add); apply_add(i*2+1, lazy[i].add); lazy[i].add = 0; } } } int calc_h(size_t nn){ int hh = 1; for (; nn > 1; ++hh, nn >>= 1); return hh; } void process_command(size_t L, size_t R, T v, int command_type){ L += n; R += n; size_t L0 = L; size_t R0 = R; push(L); push(R - 1); for (; L < R; L >>= 1, R >>= 1){ if (L & 1) apply(L++, v, command_type); if (R & 1) apply(--R, v, command_type); } build(L0); build(R0 - 1); } void fill_weight(const vector & ws){ copy(begin(ws), end(ws), begin(weight) + n); for (int i = n - 1; i > 0; --i) weight[i] = combine(weight[i*2], weight[i*2+1]); } public: SegTree(): n(0), h(1), data(), weight(), lazy() {} explicit SegTree(const vector &_weight): n(_weight.size()), h(calc_h(n)), data(2 * n, 0), weight(2 * n, 0), lazy(n) { fill_weight(_weight); } SegTree(const vector &src, const vector &_weight): n(src.size()), h(calc_h(n)), data(2 * n, 0), weight(2 * n, 0), lazy(n){ fill_weight(_weight); for (int i = 0; i < n; ++i) data[n + i] = src[i] * weight[n + i]; for (int i = n - 1; i > 0; --i) data[i] = combine(data[i*2], data[i*2+1]); } void init(const vector &_weight){ n = _weight.size(); h = calc_h(n); data.assign(2 * n, 0); weight.assign(2 * n, 0); lazy.resize(n); fill_weight(_weight); } void modify(size_t L, size_t R, T w) {process_command(L, R, w, 0);} // assign w to range [L, R) void add(size_t L, size_t R, T v) {process_command(L, R, v, 1);} // add v to range [L, R) T query(size_t L, size_t R){ L += n; R += n; push(L); push(R - 1); T ret = 0; for (; L < R; L >>= 1, R >>= 1){ if (L & 1) ret = combine(ret, data[L++]); if (R & 1) ret = combine(data[--R], ret); } return ret; } }; template void compress(const vector &src, unordered_map &zip, vector &unzip){ unzip = src; sort(unzip.begin(), unzip.end()); unzip.erase(unique(unzip.begin(), unzip.end()), unzip.end()); int i = 0; for (auto u : unzip) zip[u] = i++; }; vector calc_spans(const vector & src){ vector spans; for (int i = 1; i < src.size(); ++i) spans.push_back(src[i] - src[i - 1]); return spans; } struct Query{ int x; long long L; long long R; Query(int _x=0, long long _L=0, long long _R=0):x(_x), L(_L), R(_R){} }; int main(){ ios::sync_with_stdio(false); cin.tie(0); long long N; int Q; cin >> N; cin >> Q; vector Qs(Q); for (auto & q : Qs) cin >> q.x >> q.L >> q.R; vector LRs(2*Q); for (int i = 0; i < Q; ++i){ LRs[2*i] = Qs[i].L; LRs[2*i + 1] = Qs[i].R + 1; } LRs.push_back(N); LRs.push_back(0); vector unzip; unordered_map zip; compress(LRs, zip, unzip); auto spans= calc_spans(unzip); vector> segs(5, SegTree(spans)); vector scores(5, 0); for (const auto & q : Qs){ int cL = zip[q.L]; int cR = zip[q.R + 1]; if (q.x == 0){ long long bonus = -1; int winner = -1; for (int i = 0; i < 5; ++i){ long long score = segs[i].query(cL, cR); if (score > bonus){ bonus = score; winner = i; }else if (score == bonus){ winner = -1; } } if (winner == -1) continue; scores[winner] += bonus; scores[winner] %= mod; }else{ for (int i = 0; i < 5; ++i){ if (i + 1 == q.x){ segs[i].add(cL, cR, 1); }else{ segs[i].modify(cL, cR, 0); } } } } for (int i = 0; i < 5; ++i){ scores[i] += segs[i].query(0, zip[N]); scores[i] %= mod; } cout << scores[0]; for (int i = 1; i < 5; ++i) cout << ' ' << scores[i]; cout << endl; return 0; }