#O1103. 三维偏序

三维偏序

题目描述

给定 nn 个三元组 (ai,bi,ci)(a_i,b_i,c_i)。对每个 ii,求满足 aj≤aia_j \le a_i、bj≤bib_j \le b_i、cj≤cic_j \le c_i 的 jj 的个数(包括 ii 自身)。

输入格式

第一行两个整数 n,Kn,K,其中 KK 是每个维度的取值上界。

接下来 nn 行,每行三个整数 ai,bi,cia_i,b_i,c_i。

输出格式

共 nn 行,按输入顺序,每行一个整数,表示该点的答案。

样例 #1

样例输入 #1

3 3
1 1 1
2 2 2
1 2 1

样例输出 #1

1
3
2

数据规模与约定

数据范围 说明
1≤n≤1051 \le n \le 10^5 点数
1≤K≤1051 \le K \le 10^5 每个维度的值域
  • 先按 (a,b,c)(a,b,c) 排序去重,再用 CDQ 分治 + 树状数组统计。
  • 全部点相同的时候要用 cnt 合并。