cdq 分治小记

· · 算法·理论

引言

神奇的思路。

我们都知道归并排序，由于已经排好了左半边和右半边，想要求出这一片就很快。而 cdq 就是基于这一过程。

特性

cdq 是离线算法，往往用来解决三维偏序问题。

以 陌上花开 一题为例。假如用暴力做，时间为 O(n^2)。cdq 分治可以优化至 O(n\log^2 n)。

过程

首先将第一维按以 a,b,c 分别为 1,2,3 关键字排序。然后将大区间分成两半。分别处理左，右区间。将左，右区间按 b 排序。这个时候，左边的 a 都是不大于右边的 a 的。因为 b 具有单调性，我们用双指针法把符合条件的 b 挑选出来，并将该值的 c 放进值域树状数组。

由于 a,b 都是符合条件的。所以直接按右边区间的 c 查询即可。

注意这一题，还需要把重复的变成一个，否则会出现某些在左边，某些在右边的奇怪情况，导致答案统计不到。

限制

我们从算法的流程中可以知道，在一遍 cdq 分治中，只能有一种顺序，也就是说，只能统计到 a_i\leq a_j,b_i\leq b_j,c_i\leq c_j 的情况，并且对于值域有依赖。

代码

常数优化

  1. 每次做完一个区间后，要清理树状数组，可以考虑时间戳优化。

  2. 我们发现，对于一个小区间，值域树状数组导致即使 \log 也有 20，这个时候，n\log^2 n 显著的劣于 n^2。对于小区间，直接暴力。

  3. 这种方式很有效。直接将 sort 变成归并，带来显著的常数优化。和 2 叠加使用时要把暴力的区间也排序了。（需要注意，优化的不是复杂度）

练习

比较基础，都是在各式各样的题面内转化为该模型，将原本的限制都解除。

Mokia

第一维 time，第二维 x，第三维 y。二维前缀和拆成 4 个点。

天使玩偶

这一题要注意的比较多。

  1. 一次 cdq 只能考虑到一定顺序的，但是考虑转换大小关系，也就是将坐标用四次： (x,y),(x,inf-y),(inf-x,y),(inf-x,inf-y)，做 4 遍。（总不会有人写 4 个 cdq 吧）
  2. 卡常。
  3. 注意不要让值域触及 0。