【笔记】CDQ分治

Part 1 简介

CDQ分治，即基于时间的分治算法，最早被陈丹琦引入国内而得名。

Part 2 点对问题

1. 找到这个序列的中点

2. 将所有点对$(i, j)$ 划分为 3 类

   第一种是$1 ≤ i ≤ mid, 1 ≤ j ≤ mid$ 的点对

   第二种是$1 ≤ i ≤ mid, mid + 1 ≤ j ≤ n$ 的点对

   第三种是$mid + 1 ≤ i ≤ n, mid + 1 ≤ j ≤ n$ 的点对

3. 将$(1, n)$ 这个序列拆成两个序列$(1, mid)$ 和$(mid + 1, n)$

   会发现第一类点对和第三类点对都在这两个序列之中，递归的去解决这两类点对

4. 想方设法处理一下第二类点对的信息

Part 2.1 偏序问题

一维偏序直接sort

二维偏序第1维sort，第2维CDQ分治

三维偏序第1维sort，第2维CDQ分治，第3维数据结构

Part 2.1.1 二维偏序

有 $n$ 个元素，第 $i$ 个元素有 $a_i、b_i$ 两个属性，设 $f(i)$ 表示满足 $a_j \leq a_i$ 且 $b_j \leq b_i$ 的 $j$ 的数量。

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

我们可以把两个元素抽象成一个点 $(a,b)$, 那么我们就是求一个矩形中有多少个点。

首先我们可以按照 $x$ 轴 (a的值) 排个序，发现矩形右边的点已经不在答案的贡献里了。那么 $f(i)$ 就是在排序后的数组中找 $1\sim i-1$ 中有几个元素 $b$ 比 $b_i$ 小。

那么我们直接树状数组即可，时间复杂度 $O(n \log n)$

当我们插入一个 $b$ 值等于 $x$ 的点时，我们就令树状数组的 $x$ 位置单点 + 1，而查询数据结构里有多少个点小于 $x$ 的操作实际上就是在求前缀和

Part 2.1.2 三维偏序

有 $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$ 的数量。

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