OI XXXIII - des (Alt)

// https://szkopul.edu.pl/problemset/problem/a0qKqyZmbnu2gCu_P8LSmKtV/site/?key=statement

#include <bits/stdc++.h>
using namespace std;

const int MAXL = 1000006;
int mx[4 * MAXL], sl[4 * MAXL], al[4 * MAXL];

void app_set(int nd, int v) {
    mx[nd] = v;
    sl[nd] = v;
    al[nd] = 0;
}
void app_add(int nd, int v) {
    mx[nd] += v;
    al[nd] += v;
}

void push(int nd) {
    if (sl[nd] != -1) {
        int v = sl[nd] + al[nd];
        app_set(nd * 2, v);
        app_set(nd * 2 + 1, v);
        sl[nd] = -1;
        al[nd] = 0;
    } else if (al[nd]) {
        app_add(nd * 2, al[nd]);
        app_add(nd * 2 + 1, al[nd]);
        al[nd] = 0;
    }
}

int SZ;

void seg_set(int nd, int lo, int hi, int l, int r, int v) {
    if (r <= lo || hi <= l) return;
    if (l <= lo && hi <= r) {
        app_set(nd, v);
        return;
    }
    push(nd);
    int mid = (lo + hi) / 2;
    seg_set(nd * 2, lo, mid, l, r, v);
    seg_set(nd * 2 + 1, mid, hi, l, r, v);
    mx[nd] = max(mx[nd * 2], mx[nd * 2 + 1]);
}

void seg_add(int nd, int lo, int hi, int l, int r, int v) {
    if (r <= lo || hi <= l) return;
    if (l <= lo && hi <= r) {
        app_add(nd, v);
        return;
    }
    push(nd);
    int mid = (lo + hi) / 2;
    seg_add(nd * 2, lo, mid, l, r, v);
    seg_add(nd * 2 + 1, mid, hi, l, r, v);
    mx[nd] = max(mx[nd * 2], mx[nd * 2 + 1]);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    vector<int> d(m), x(m), y(m);
    vector<int> coords;
    for (int i = 0; i < m; i++) {
        cin >> d[i] >> x[i] >> y[i];
        coords.push_back(x[i]);
        coords.push_back(y[i]);
    }
    if (m == 0) {
        for (int i = 0; i < n; i++)
            cout << "0\n";
        return 0;
    }
    sort(coords.begin(), coords.end());
    coords.erase(unique(coords.begin(), coords.end()), coords.end());
    SZ = (int)coords.size() - 1;
    vector<vector<pair<int, int>>> iv(n + 1);
    for (int i = 0; i < m; i++) {
        int li = (int)(lower_bound(coords.begin(), coords.end(), x[i]) - coords.begin());
        int ri = (int)(lower_bound(coords.begin(), coords.end(), y[i]) - coords.begin());
        iv[d[i]].emplace_back(li, ri);
    }
    for (int dd = 1; dd <= n; dd++)
        sort(iv[dd].begin(), iv[dd].end());
    memset(sl, 0xFF, sizeof(sl));
    vector<int> ans(n + 1);
    for (int i = n; i >= 1; i--) {
        if (iv[i].empty()) {
            seg_set(1, 0, SZ, 0, SZ, 0);
            ans[i] = 0;
        } else {
            int prev = 0;
            for (auto& [li, ri] : iv[i]) {
                if (prev < li) seg_set(1, 0, SZ, prev, li, 0);
                seg_add(1, 0, SZ, li, ri, 1);
                prev = ri;
            }
            if (prev < SZ) seg_set(1, 0, SZ, prev, SZ, 0);
            ans[i] = mx[1];
        }
    }
    for (int i = 1; i <= n; i++)
        cout << ans[i] << '\n';
    return 0;
}