题目背景

这是 P3810 【模板】三维偏序 / 陌上花开 前置题。

保证没有重复点，数据随机，多种方法可以完成。

题目描述

有 $n$ 个元素，第 $i$ 个元素有 $a_i,b_i$ 两个属性，设 $f(i)$ 表示满足 $a_j \leq a_i$ 且 $b_j \leq b_i$ 且 $j \ne i$ 的 $j$ 的数量。

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

保证没有重复点。

输入格式

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

接下来 $n$ 行，每行三个整数 $a_i ,b_i$，分别表示两个属性值。

输入数据保证没有重复点（即不存在 $i\ne j$ ,$a_i=a_j$ 且 $b_i=b_j$ 的两个点）

输出格式

一个整数，表示两个数的积

5 10
1 2
3 4
1 3
2 5
10 10

1
1
2
0
1

样例1解释

将所有点排序，可以得到如下：

1 2 f[i]=0
1 3 f[i]=1
2 5 f[i]=2
3 4 f[i]=2
10 10 f[i]=4

那么 f[i]=0 的个数为 1 ，f[i]=1/2/3/4 第个数依次为 1 2 0 1 , 所以答案就是为 1 1 2 0 1.

数据规模与约定

对于所有数据，保证 $1 \leq n \leq 10^5$，$1 \leq a_i, b_i\le k \leq 2 \times 10^5$。

$Subtask1: n\le 10^3$ , $20$ 分

$Subtask2: n\le 5\times 10^4$, $30$ 分

$Subtask3: n\le 10^5$ ，$50$ 分

数据随机，于是就会有多种做法： K-D tree 、CDQ 、 bitset 、数据结构等