P3810 【模板】三维偏序（陌上花开） 分析

· · 个人记录

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

我们可以利用一些技巧压掉第一维度，即：将这些元素按主键元素排序，于是，对于所有的 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 的。用一个双指针即可。