P3810 CDQ

#include <bits/stdc++.h>
 
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#include <ext/pb_ds/hash_policy.hpp>
#include <ext/pb_ds/priority_queue.hpp>
 
using namespace std;
using namespace __gnu_pbds;
 
#ifdef LOCAL
void dbg() { cerr << '\n'; }
template<class T, class ...U> void dbg(T a, U ...b) { cerr << a << ' ', dbg(b...); }
template<class T> void org(T l, T r) { while (l != r) cerr << *l++ << ' '; cerr << '\n'; }
#define debug(args...) (dbg("(" + string(#args) + ") = (", args, ")"))
#define orange(args...) (cerr << "[" + string(#args) + ") = ", org(args))
#else
#pragma GCC optimize("O3,unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
#define debug(...) ((void)0)
#define orange(...) ((void)0)
#endif
template<class T> bool chmin(T &a, T b) { return b < a and (a = b, true); }
template<class T> bool chmax(T &a, T b) { return a < b and (a = b, true); }
#define all(v) begin(v), end(v)
#define rall(v) rbegin(v), rend(v)
#define ff first
#define ss second
 
template<class T>
using BST = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
using i64 = long long;
using u64 = unsigned long long;
using pii = pair<int, int>;
using pll = pair<long long, long long>;
using pdd = pair<double, double>;
 
constexpr i64 INF = 1ll << 60;
constexpr i64 mod = 998244353;
constexpr double eps = 1e-10;
 
int add() { return 0; }
int mul() { return 1; }
template<class... U> int add(int a, U... b) { return (a += add(b...)) >= mod ? a - mod : a; }
template<class... U> int mul(int a, U... b) { return (i64)a * mul(b...) % mod; }

struct BIT {
    vector<int> v;
    int n;
    BIT(int _n) : n(_n), v(_n + 1) {}
    int lowbit(int x) { return x & -x; }
    void add(int p, int x) {
        for (int i = p; i <= n; i += lowbit(i))
            v[i] += x;
    }
    int que(int p) {
        int r = 0;
        for (int i = p; i > 0; i -= lowbit(i))
            r += v[i];
        return r;
    }
};

void solve() {
    int n, m;
    cin >> n >> m;

    vector<array<int, 3>> A(n);
    for (auto &[a, b, c] : A) {
        cin >> a >> b >> c;
    }

    vector<int> ord(n);
    vector<int> ans(n);
    iota(all(ord), 0);
    sort(all(ord), [&](int a, int b) -> bool { return A[a] < A[b]; } );

    BIT bit(m);
    function<void(int, int)> CDQ = [&](int l, int r) {
        if (r - l <= 1) return;

        int mid = l + r >> 1;
        CDQ(l, mid), CDQ(mid, r);

        vector<int> tmp;
        for (int i = l, j = mid; i < mid or j < r; ) {
            while (i < mid and (j == r or A[ord[i]][1] <= A[ord[j]][1])) {
                bit.add(A[ord[i]][2], 1);
                tmp.push_back(ord[i]);
                i++;
            }
            if (j < r) {
                ans[ord[j]] += bit.que(A[ord[j]][2]);
                tmp.push_back(ord[j]);
                j++;
            }
        }

        for (int i = l; i < mid; i++) bit.add(A[ord[i]][2], -1);
        copy(all(tmp), ord.begin() + l);
    };
    CDQ(0, n);

    for (int l = 0, r = 0; l < n; l = r) {
        while (r < n and A[ord[l]] == A[ord[r]]) {
            r++;
        }
        if (r - l > 1) {
            for (int i = l; i < r; i++) {
                ans[ord[i]] = ans[ord[r - 1]];
            }
        }
    }

    vector<int> cnt(n);
    for (int i = 0; i < n; i++) {
        cnt[ans[i]]++;
    }

    for (int i = 0; i < n; i++) {
        cout << cnt[i] << '\n';
    }
}

signed main() {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    signed T = 1;
    // cin >> T;
    while (T--) solve();
    return 0;
}
 
/*
 

*/