OI XXXIII - des (Alt2)

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

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 500005;
const int MAX_NODES = 4000005;

vector<pair<int, int>> days[MAXN];

int tree_max[MAX_NODES];
int tree_lazy[MAX_NODES];
int ans[MAXN];

void update(int node, int l, int r, int ql, int qr, int val) {
    if (ql <= l && r <= qr) {
        tree_lazy[node] += val;
        tree_max[node] += val;
        return;
    }
    int mid = l + (r - l) / 2;
    if (ql <= mid) update(2 * node, l, mid, ql, qr, val);
    if (qr > mid) update(2 * node + 1, mid + 1, r, ql, qr, val);
    tree_max[node] = tree_lazy[node] + max(tree_max[2 * node], tree_max[2 * node + 1]);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0);

    int n, m;
    cin >> n >> m;

    vector<int> coords;
    coords.reserve(2 * m);

    for (int i = 0; i < m; i++) {
        int d, x, y;
        cin >> d >> x >> y;
        days[d].push_back({x, y});
        coords.push_back(x);
        coords.push_back(y);
    }

    if (m > 0) {
        sort(coords.begin(), coords.end());
        coords.erase(unique(coords.begin(), coords.end()), coords.end());

        for (int i = 1; i <= n; i++) {
            for (auto& p : days[i]) {
                p.first = lower_bound(coords.begin(), coords.end(), p.first) - coords.begin();
                p.second = lower_bound(coords.begin(), coords.end(), p.second) - coords.begin() - 1;
            }
        }
    }

    int MAX_LEAF = max(0, (int)coords.size() - 2);

    int j = 0;
    for (int i = 1; i <= n; i++) {
        while (j < n) {
            for (auto& p : days[j + 1]) {
                update(1, 0, MAX_LEAF, p.first, p.second, 1);
            }

            if (tree_max[1] == (j + 1) - i + 1) {
                j++;
            } else {
                for (auto& p : days[j + 1]) {
                    update(1, 0, MAX_LEAF, p.first, p.second, -1);
                }
                break;
            }
        }

        ans[i] = j - i + 1;

        if (ans[i] > 0) {
            for (auto& p : days[i]) {
                update(1, 0, MAX_LEAF, p.first, p.second, -1);
            }
        } else {
            j = i;
        }
    }

    for (int i = 1; i <= n; i++) {
        cout << ans[i] << "\n";
    }

    return 0;
}