#45. 三维偏序CDQ分治

    ID: 45 传统题 2000ms 256MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>数据结构树套树模板三维偏序CDQ 分治

三维偏序CDQ分治

题目描述

n n 个元素,第 i i 个元素有 ai a_i bi b_i ci c_i 三个属性,设 f(i) f(i) 表示满足 ajai a_j \leq a_i bjbi b_j \leq b_i cjci c_j \leq c_i j j 的数量。

对于 d[0,n) d \in [0, n) ,求 f(i)=d f(i) = d i i 的数量。

输入格式

第一行两个整数 n n k k ,分别表示元素数量和最大属性值。

之后 n n 行,每行三个整数 ai a_i bi b_i ci c_i ,分别表示三个属性值。

输出格式

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

样例

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
3
1
3
0
1
0
1
0
0
1

数据范围与提示

1n100000,1k200000 1 \leq n \leq 100000, 1 \leq k \leq 200000