提高⏱ 1000ms💾 256MB#P8014

题目描述

给定 $n$ 个三元组 $(a_i,b_i,c_i)$,统计有多少个有序对 $(i,j)$$i \ne j$)满足 $a_i \le a_j,\ b_i \le b_j,\ c_i \le c_j$。请用 CDQ 分治等高效方法。

输入格式

第一行一个整数 $n$;接下来 $n$ 行每行三个整数 $a_i,b_i,c_i$

输出格式

一行一个整数,即有序对个数。

数据范围

$$1 \le n \le 10^5,\ 0 \le a_i,b_i,c_i \le 2\times 10^9$$

样例输入 #1
3
1 2 3
4 5 6
1 2 4
样例输出 #1
3
样例输入 #2
4
0 0 0
0 0 0
1 1 1
0 0 0
样例输出 #2
9