P3810 [Template] Three-Dimensional Partial Order / Mo Shang Hua Kai

This is a template problem. You can solve it using bitset, CDQ divide-and-conquer, KD-tree, etc.

There are $ n $ elements. The $ i $-th element has three attributes $ a_i, b_i, c_i $. Let $ f(i) $ be the number of $ j $ such that $ a_j \leq a_i $, $ b_j \leq b_i $, $ c_j \leq c_i $, and $ j \ne i $. For all $ d \in [0, n) $, find the number of $ i $ such that $ f(i) = d $.

The first line contains two integers $ n,k $, denoting the number of elements and the maximum attribute value. The next $ n $ lines each contain three integers $ a_i ,b_i,c_i $, representing the three attribute values.

Output $ n $ lines. The $ d + 1 $-th line contains the number of $ i $ such that $ f(i) = d $.

For all testdata, it is guaranteed that $ 1 \leq n \leq 10^5$，$1 \leq a_i, b_i, c_i \le k \leq 2 \times 10^5 $. Translated by ChatGPT 5