题意

有 $n$ 个元素，第 $i$ 个元素有 $a_i,b_i,c_i$ 三个属性，设 $f(i)$ 表示满足 $a_j \leq a_i$ 且 $b_j \leq b_i$ 且 $c_j \leq c_i$ 且 $j \ne i$ 的 $j$ 的数量。 对于 $d \in [0, n)$ ，求 $f(i) = d$ 的数量。

$1 \leq n \leq 10^5,1 \leq a_i, b_i, c_i \le k \leq 2 \times 10^5$ 。

题解

这里用 CDQ 分治。

对于每个点，先按 $a$ 为关键字排序。然后分治。

在分治的过程中，前半段的 $a$ 一定小于等于后半段 $a$ ，那就无忌惮地再按 $b$ 排序（此时已经变成二维偏序了），然后树状数组维护 $c$ 。

代码

const int N = 1e5 + 10, K = 2e5 + 10;

int n, m, k;
struct node {
	int a, b, c, cnt, ans;
	bool operator < (const node &x) const {
		return a < x.a || (a == x.a && (b < x.b || (b == x.b && (c < x.c))));
	}
}a[N], b[N];
int t[K];

void modify(int x, int val) {for (; x <= K - 10; x += x & -x) t[x] += val;}
int query (int x) {int ans = 0; for (; x; x -= x & -x) ans += t[x]; return ans;} 

int ans[N];

bool cmp (node a, node b){return a.b < b.b || (a.b == b.b && (a.c < b.c));}

void CDQ (int l, int r) {
	if (l == r) return;
	int mid = (l + r) >> 1;
	CDQ (l, mid), CDQ (mid + 1, r);
	sort (a + l, a + 1 + mid, cmp), sort (a + 1 + mid, a + 1 + r, cmp);
	int i, j = l;
	for (int i = mid + 1; i <= r; i ++) {
		while (a[i].b >= a[j].b && j <= mid) {
			modify (a[j].c, a[j].cnt);
			j++;
		}
		a[i].ans += query(a[i].c);
	}
	for (i = l; i < j; i++) modify(a[i].c, -a[i].cnt);
}

int main() {
//	freopen(".in", "r", stdin);
//	freopen(".out", "w", stdout);
	scanf ("%d%d", &n, &k);
	for (int i = 1; i <= n; i++)
		scanf ("%d%d%d", &b[i].a, &b[i].b, &b[i].c);
	sort (b + 1, b + 1 + n);
	for (int i = 1, cnt = 0; i <= n; i++) {
		cnt ++;
//		if (b[i] != b[i + 1])
		if (b[i].a != b[i + 1].a || b[i].b != b[i + 1].b || b[i].c != b[i + 1].c) {
			a[++m] = b[i];
			a[m].cnt = cnt;
			cnt = 0;
		}
	}
	CDQ (1, m);
	for (int i = 1; i <= m; i++)
		ans[a[i].cnt + a[i].ans - 1] += a[i].cnt;
	for (int i = 0; i < n; i++)
		printf ("%d\n", ans[i]);
    return 0;
}