P3810 CDQ
unknown
c_cpp
a year ago
3.7 kB
23
Indexable
Never
#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; } /* */