本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-02-03 08:22:36

三维偏序实际上就是经典题目 —— 逆序对 的升级版。但是前者是三维，而后者只是一维（啥比了，逆序对是二维的）。

我们可以利用一些技巧压掉第一维度，即：将这些元素按主键元素排序，于是，对于所有的 $i \lt j$，都有 $a_i \le a_j$，于是第一维被压掉了。

接下来我们考虑怎么压掉第二维，以转化到我们熟悉的逆序对。这里要用到 CDQ 分治。

CDQ 分治适用于区间上的一些操作：通过将大区间上的操作分割成小操作并归纳，我们可以免去处理合并的问题，只考虑对区间进行统计。

例如此题中，我们在分治过程中得到了两个子区间，现在我们要做的就是统计这两个子区间之间的三维偏序数量。

不妨将两个区间排序，设为 $L$ 与 $R$，那么对于所有 $0 \le i, j \le T$，都有 $a(L_i) \le a(R_j)$（因为 $i$ 和 $j$ 在原序列中是增的）。我们接下来要找的是满足 $b_i \le b_j$ 且 $c_i \le c_j$ 的。用一个双指针即可。