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

2huk · 2024-08-11 20:35:27 · 题解

考虑二维偏序。

我们将所有点按某一维排序，然后按照这一位扫描线。这样操作的目的是把这一维变成时间维。

然后维护一个树状数组，在扫描的过程中做在线的一维偏序。这是简单的。

这给了我们一个启示：离线的 x 维偏序与在线的 x - 1 维偏序的难度相同。做法就是将某一维转化成时间维。

同理对于三维偏序我们要做在线的二维偏序。考虑 cdq 分治。

首先按 x 排序。

定义函数 \text{solve}(l, r) 表示求有多少对 (i, j) 满足 l \le i \le j \le r 且满足三维偏序的要求。那么我们执行三个步骤：

• 计算有多少 (i, j) 满足 l \le i \le mid 且 mid < j \le r。

对于第三个，显然左边的 x 一定小于右边的 x。所以这一维无需考虑。

我们再将左右两边分别按 y 排序，然后双指针扫描。这样就满足 y 的条件。

再套一个树状数组就能满足 z 的条件。