【模板】三维偏序(陌上花开)

题目背景

这是一道模板题,可以使用 bitset,CDQ 分治,KD-Tree 等方式解决。

题目描述

有 $ 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 $ 的数量。

输入输出格式

输入格式


第一行两个整数 $ n,k $,表示元素数量和最大属性值。 接下来 $ n $ 行,每行三个整数 $ a_i ,b_i,c_i $,分别表示三个属性值。

输出格式


$ n $ 行,第 $ d + 1 $ 行表示 $ f(i) = d $ 的 $ i $ 的数量。

输入输出样例

输入样例 #1

10 3
3 3 3
2 3 3
2 3 1
3 1 1
3 1 2
1 3 1
1 1 2
1 2 2
1 3 2
1 2 1

输出样例 #1

3
1
3
0
1
0
1
0
0
1

说明

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