OI XXXIII - des (Mle2)

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

// 45/100 points

#include <bits/stdc++.h>

constexpr int sizik = 500 * 1001;

#define ar std::array

typedef std::pair<int, int> S;
typedef std::vector<S> P;
int n, m;

std::pair<S, bool> cr(const S& s1, const S& s2) {
    if (s1.first > s2.first) return cr(s2, s1);
    if (s2.first > s1.second) return {{}, false};
    if (s2.second <= s1.second) {
        return {s2, true};
    }
    return {{s2.first, s1.second}, true};
}

P merge(const P& a, const P& b) {
    if (a.size() > b.size()) {
        return merge(b, a);
    }
    const int n1 = a.size(), n2 = b.size();

    P ans;

    if (a.empty() || b.empty()) {
        return ans;
    }

    if (a[0].first == -1 && b[0].first == -1) {
        return ans;
    }
    if (a[0].first == -1) {
        return b;
    }
    if (b[0].first == -1) {
        return a;
    }

    int j = 0;
    for (int i = 0; i < n1; i++) {
        while (j < n2) {
            auto res = cr(a[i], b[j]);
            if (res.second) {
                ans.push_back(res.first);
                if (b[j].second > a[i].second) {
                    break;
                } else {
                    j++;
                }
            } else {
                if (b[j].first > a[i].first) {
                    break;
                } else {
                    j++;
                }
            }
        }
    }
    return ans;
}

P pg[sizik];

namespace window_manager {
std::vector<P> s1, s2;
int mid;

void init() {
    s1.clear();
    s2.clear();
    mid = 0;
}

void push(const P& val) {
    if (s2.empty())
        s2.push_back(val);
    else
        s2.push_back(merge(s2.back(), val));
}

P query() {
    if (s1.empty() && s2.empty()) return {{-1, -1}};
    if (s1.empty()) return s2.back();
    if (s2.empty()) return s1.back();
    return merge(s1.back(), s2.back());
}

void pop(int current_L, int current_R) {
    if (s1.empty()) {
        mid = current_R;
        P curr;
        bool first = true;

        for (int k = current_R; k >= current_L + 1; k--) {
            if (first) {
                curr = pg[k];
                first = false;
            } else {
                curr = merge(pg[k], curr);
            }
            s1.push_back(curr);
        }
        s2.clear();
    } else {
        s1.pop_back();
    }
}

void clear() {
    s1.clear();
    s2.clear();
}
} // namespace window_manager

void solve_b1() {
    std::cin >> n >> m;

    for (int i = 1; i <= m; i++) {
        int d, x, y;
        std::cin >> d >> x >> y;
        pg[d].push_back({x, y - 1});
    }
    for (int i = 1; i <= n; i++) {
        std::sort(pg[i].begin(), pg[i].end());
    }

    window_manager::init();

    int x = 1;
    window_manager::mid = 0;
    window_manager::push(pg[1]);

    for (int i = 1; i <= n; i++) {
        if (x < i) {
            x = i;
            window_manager::clear();
            window_manager::mid = i - 1;
            window_manager::push(pg[i]);
        }

        while (x < n) {
            P current = window_manager::query();

            if (current.empty()) break;

            P next_candidate = merge(current, pg[x + 1]);

            if (!next_candidate.empty()) {
                x++;
                window_manager::push(pg[x]);
            } else {
                break;
            }
        }

        P res = window_manager::query();

        if (res.empty()) {
            std::cout << "0\n";
        } else {
            std::cout << (x - i + 1) << "\n";
        }

        window_manager::pop(i, x);
    }
}

int32_t main() {
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);

    solve_b1();

    return 0;
}