CDQ 分治

Zhl2010 · 2024-11-16 17:01:59 · 算法·理论

---
 CCCC   DDDD    QQQQ
C    C  D   D  Q    Q
C       D   D  Q    Q
C       D   D  Q    Q
C    C  D   D  Q   Q
 CCCC   DDDD    QQQQ
---

一、一维偏序

给你一个长度为 n 的序列，求出每个元素在序列中比其小的元素数目。

这是最为简单的偏序问题，处理方法也很简单：将原序列升序排序，当然如果有重复元素，我们要适当进行去重处理。

有 n 个元素，第 i 个元素有 ai,bi 两个属性，求出每个下标 i，满足 j != i，aj ≤ ai 且 bj ≤ bi 的 j 的数目

先按照 a_i 进行排序，然后对bi进行归并排序

归并排序。

归并排序时，序列被划分为 [l, mid] 和 [mid + 1, r] 两个序列

虽然按照 b_i 进行归并排序会导致 a_i 的顺序混乱，但是两个序列仍然满足左边序列的 a_i 不大于右边序列的 a_i

当我们双指针合并两个序列时，当要存放右边序列的元素时，可以根据左边指针和左边界的相对位置计算其贡献

时间复杂度 O(nlogn)。

CDQ通俗一点说就是三句话：

1.递归前一半

2.判断前一半对于后一半的影响

3.递归后一半

明显更简单。

先按照 a_i 进行排序，然后开树状数组维护当前遍历位置之前值小于等于 b_i 的元素数目遍历按照第一维排序后的序列，ans_i = query(b_i)

时间复杂度 O(nlogn)

【模板】二维偏序

例题：\textcolor{purple}{3810 【模板】三维偏序（陌上花开）}。

有 n 个元素，第 i 个元素有 a_i,b_i,c_i 三个属性，设 f(i) 表示满足 a_j \leq a_i 且 b_j \leq b_i 且 c_j \leq c_i 且 j \ne i 的 j 的数量。

对于 d \in [0, n) ，求 f(i) = d 的数量。

虽然问题变成了三维偏序，但是基本思路还是按照某个维度排序，然后计算前面对后面的影响，通过这样的策略，达到将问题降维的效果。

CDQ 分治是以曾经的 IOI 选手陈丹琦命名的一种离线的分治算法，主要用于解决偏序问题。

CDQ 分治解决三维偏序的流程有归并排序和树状数组两种做法，我们这里给出树状数组做法。

先按一维属性排序和去重。
假设三维分别是 x，y，z，先按 x 排序。
然后去掉重复元素，记录每个元素出现的次数 cnt CDQ 分治：类似归并排序的思想，先按第一维属性划分为前一半和后一半，回归时计算前一半对后一半的影响。
分治后每次将前一半、后一半分别按 y 排序。虽然现在 x 的顺序被打乱了，但是前一半的 x 还是都小于后一半的，所以只计算前一半对后一半的偏序关系，是不会受到 x 影响的。
用双指针 i,j 来维护前一半和后一半，每次将 j 后移一位时，若 y_i <= y_j，则不断后移 i，并不断将 z_i 加入树状数组。然后再查询树状数组中有多少数 <=z_j，即 <= e_j 的偏序数量。

注意：最后要清空树状数组。

时间复杂度 O (nlog^2n)

代码（不是我的，我的码风有点。。。，但我加了注释），想看的就看。