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

    ID: 2743 Type: RemoteJudge 1000ms 500MiB Tried: 14 Accepted: 11 Difficulty: 6 Uploaded By: Tags>树状数组cdq 分治O2优化分治排序概率论统计K-D Tree

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

题目背景

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

题目描述

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

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

输入格式

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

接下来 n n 行,每行三个整数 ai,bi,ci a_i ,b_i,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

提示

1n105 1 \leq n \leq 10^51ai,bi,cik2×1051 \leq a_i, b_i, c_i \le k \leq 2 \times 10^5