从归并排序讲起

\(mergesort(l, r)\)：对序列下表区间 \([l, r]\) 内元素按值进行排序

• \(mid = \frac{1}{2}(l + r)\)；
• \(mergesort(l, mid)\)；
• \(mergesort(mid + 1, r)\)；
• 双指针合并两个左右有序区间：\(merge(l, mid + 1, r + 1)\)

不难发现，归并排序巧妙地避开了对区间进行排序本身，把问题完全转变为了两个有序区间的合并问题。只要能解决后者，那么前者就解决了。这能不能给我们带来一些启发呢？

偏序问题

对于两个 \(k\) 元组 \(t_1: \langle x_1, x_2, \dots x_k \rangle, \ t_2: \langle y_1, y_2, \dots y_k \rangle\)，如果 \(\forall i \in [1, k]\)，满足 \(x_i < y_i\)，那么我们称 \(\langle t_1, t_2 \rangle\) 构成一组 \(k\) 维偏序（有的地方可能会把 \(<\) 定义成 \(\le\)）。

void divideConquer(int headPt, int tailPt) {
    if (headPt == tailPt)
        return;
    int midPt = (headPt + tailPt) >> 1;
    divideConquer(headPt, midPt); divideConquer(midPt + 1, tailPt);
    int j = headPt; // j: 左区间中指针；i: 右区间中指针
    for (int i = midPt + 1; i <= tailPt; i++) {
        for (; j <= midPt && arr[j].b < arr[i].b; j++) 
            add(arr[j].c, 1);
        // 统计总三维偏序对数量（树状数组中 c 维小于当前的数量）
        ans += prefixSum(arr[i].c - 1);
    }
    // 撤销对树状数组的更改
    for (int i = headPt; i < j; i++)
        add(arr[i].c, -1);
    // 按 b 维合并左右有序区间（cmpSnd 为按照 b 维从小到大排序的比较函数）
    inplace_merge(arr + headPt, arr + midPt + 1, arr + tailPt + 1, cmpSnd);
}

动态数据结构问题？

接下来我们讨论这个思想怎么跟动态数据结构问题扯上联系。

我们来考虑一下动态数据结构问题中回答查询的本质：即计算初始数据和本次查询之前，所有修改对该查询造成的影响。那么我们能不能借助分治思想使得修改和查询不要混在一起呢？

\(solve(l, r)\)：\(\forall k \in [l, r]\)，若第 \(k\) 项操作是查询，则计算 \([l, k - 1]\) 中修改对其造成的影响：

• \(mid = \frac{1}{2}(l + r)\)；
• \(solve(l, mid)\)；
• \(solve(mid + 1, r)\)；
• 计算第 \([l, mid]\) 项操作中所有修改对 \([mid + 1, r]\) 中所有查询造成的影响。

这样一来，我们便将 “计算操作集区间 \([l, r]\) 内所有查询” 这一问题转换为了 “计算左区间中所有修改对右区间中所有查询造成影响”。换言之，以 \(\mathcal{O}(\log{n})\) 的代价，我们成功地将一个动态问题转换成了静态问题。

我们仿照之前来对这一算法的正确性进行分析（同时也可以看出运用这一思想对原问题的一些要求）。设第 \(k\) 项操作是查询，则：

• 若 \(k \le mid\)，则 \(solve(l, mid)\) 已经计算了第 \([l, k - 1]\) 项操作中所有修改对当前查询的影响；
• 若 \(k > mid\)，则 \(solve(mid + 1, r)\) 已经计算了第 \([mid + 1, k − 1]\) 项操作中所有修改对当前查询操作的影响。只要这一影响满足可加性且满足交换律，并且不同修改操作造成的影响互相独立，直接加上最后一项计算就可以得到第 \([l, k − 1]\) 项操作中所有修改对当前查询的影响。

那么接下来我们就来看几个例子吧。

优化动态规划

小结

通过上面的例题，我们大致领略了 CDQ 分治这一思想的几个神奇作用，即 以 \(\mathcal{O}(\log{n})\) 复杂度的代价：

• 将区间内的问题转化为两个有序区间之间的问题；
• 将高维的问题维度降低一维；
• 将动态数据结构问题转化成静态数据结构问题。

动态二分图判定

给定一张 \(n\) 个点的图，在 \(T\) 时间内一些边会在 \(s_i\) 时刻出现，并在 \(t_i\) 时刻消失。询问每一个时刻该图是否是二分图。

数据范围：均在 \(10^5\) 级别。

题目链接：BZOJ 4025: 二分图 | 如果挂了试试这个

首先，判断是否构成二分图的本质即判断是否存在奇环。一张无向图不存在奇环是该图为二分图的充要条件。那么如何维护奇环信息？我们可以用带权的并查集解决，即在并查集中记录一个深度，如果在连边时两点深度加起来在加 \(1\) 是奇数的话，就说明存在奇环了（大家可以想想为什么）。

现在问题来了，并查集中加边容易删边难，这可怎么办 QAQ。

首先，对于元素又有插入又有删除这一特性，说明每一个元素都有一个存活的时间区间（在这道题里面是直接把存活区间给出了）。对于更一般的情况，我们可以对于每一个元素预处理出时间区间，然后对时间区间进行分治。

假设一共有 \(q\) 次询问（即 \(q\) 个事件），考虑对完整时间区间 \([1, q]\) 建一棵线段树，那么对于时间点的询问即询问这棵线段树的叶子节点上的状态；而对于边的修改则是对线段树上对应区间上的修改。这样问题就转换为对于一个时间区间加边和查询叶子节点，也就不存在删边这种操作了。而整个分治过程本质上就是对这一棵线段树做先序遍历。

\(solve(l, r, Q)\)：对于时刻 \([l, r]\)，操作集为 \(Q\)，满足 \(\forall q \in Q\)，其存活时间区间与当前分治的时间区间交集非空；而这个函数的作用为对于 \([l, r]\) 内每个时刻，判断此时图是否是二分图。操作集 \(Q\) 中元素 \(q\) 带有 \(4\) 个属性：\(\langle u, v, l, r \rangle\)。其中，\(u, v\) 代表边的两个端点，而 \(l, r\) 代表出现和消失时刻。我们可以考虑如下算法：

• \(mid = \frac{1}{2} (l + r)\)，并新建两个空操作集 \(Q_L, Q_R\)；
• 遍历 \(q \in Q\)：
  • 若 \(q.l = l \land q.r = r\)（说明这一操作对其子树中所有叶子节点都有影响，那么直接加边）：
    • 并查集中合并 \(q.u\) 和 \(q.v\)，并判断是否出现奇环；
    • 存在奇环？说明时间区间 \([l, r]\) 都凉了，均标记答案为否！撤销对并查集的操作并回溯（所以我们需要可撤销并查集，其实也很简单，就搞一个栈记录一下操作之前值的情况然后撤销的时候弹栈就好了）；
  • 若 \(q.l \le mid\)：令 \(q.r = \min⁡(q.r, mid)\)，并把 \(q\) 放入 \(Q_L\)；
  • 若 \(q.r > mid\)：\(q.l = \max⁡(q.l, mid + 1)\)，并把 \(q\) 放入 \(Q_R\)；
• 若 \(l = r\)，标记答案为是，撤销对并查集的操作并回溯；
• \(solve(l, mid, Q_L)\)；
• \(solve(mid + 1, r, Q_R)\)；
• 撤销对并查集的操作并回溯。

这样一来，我们就成功避免了删除操作，从而更容易地得以解决问题。大家可以结合演示文稿里面的图示以方便理解。

最后附上 我的代码 以供参考。我的写法实际上是没有建出线段树的，当然也有另外建出线段树的写法，大家也可以去了解一下。

虚假的强制在线

这一启发来自于 Codeforces 上一道有趣的题目。

给定一个初始无边的含有 \(n\) 个点的无向图（标号从 \(1\) 开始），共 \(q\) 次操作。操作有两种形式（其中 \(last\) 代表上一次 \(2\) 类操作的结果）：

• \(1 \ x \ y \ (1 \le x, y \le n, \ x \neq y)\)：在点 \((x + last - 1) \bmod (n + 1)\) 和点 \((y + last - 1) \bmod (n + 1)\) 间添加一条无向边；
• \(2 \ x \ y \ (1 \le x, y \le n, \ x \neq y)\)：查询点 \((x + last - 1) \bmod (n + 1)\) 和点 \((y + last - 1) \bmod (n + 1)\) 是否连通。

数据范围：\(2 \le n, q \le 10^5\)

题目链接：Codeforces 1217F: Forced Online Queries Problem

虽说这道题看起来强制在线了，但是 \(last \in [0, 1]\)，其实可能的操作种数顶多就 \(2q\) 个。因此我们不妨考虑把所有操作都加入线段树分治，然后处理的时候只选取有效的那个处理。

但是怎么判这个有效呢？我们是不是只有在执行完其之前最接近的 \(2\) 类操作才能知道当前操作哪一个有效。换言之，只要在分治过程中能保证在处理每一条边前在其前面的 \(2\) 类操作已经被处理过就行了。由于查询都在叶子上，所以我们单独开一个数组记录第 \(i\) 时刻的查询是什么（即直接记录在线段树的叶子上）。

我们可以施加一点小技巧。原本边的出现时间是区间 \((s, t)\)，我们现在把它改成 \((s + 1, t)\)。这一修改导致的结果非常微妙：首先，在 \(s\) 时刻的操作其实是加边，不会同时进行查询，因此这一修改不会影响答案；其次，这样的修改保证了我们在把这一条边加入并查集是，\(s\) 时刻对应的叶子节点一定是被遍历过的，即我们已经知道了 \(last\) 确切的值，因此我们就可以判断出哪些操作是有效的了。

详细的实现大家可以参考一下 我的代码。

静态区间第 \(k\) 小

对于一个长度为 \(n\) 的数列，现有 \(q\) 次询问。每次询问给出 \(l, r, k\)，试求数列中下标在 \([l, r]\) 中第 \(k\) 小的数的数值。

数据范围：\(1 \le n \le 10^5, \ 1 \le q \le 5 \times 10^3\)

题目链接： POJ 2104: Kth Number

主席树裸题？

如果是对于单次查询，我们显然是可以先对区间进行预处理然后进行二分的。一种显而易见的思路就是将数值离散化然后开一个数组来记录每一个值在区间内出现的次数然后对前缀和进行二分。但是，当我们面对多个询问的时候，如果对每一个询问都进行预处理然后再二分，这样的复杂度显然是无法接受的。

不难发现对于每个询问其实预处理的过程都是大致相同的。那么我们是否可以对多个询问同时进行二分操作呢？

假设题目给定了由 \(n\) 个询问组成的一个询问集合 \(Q\)，并且我们知道所有出现过的数值的区间为 \([l, r]\)。二分过程中，我们记 \(mid = \frac{1}{2}(l+r)\)。在每一层递归中，我们首先对于 \(Q\) 内每一个询问进行处理，求得该询问区间中数值在 \([l, mid]\) 范围内的值的个数 \(cnt\)。接下来，我们以此将 \(Q\) 中的询问分为两类：\(cnt \ge k\) 的以及 \(cnt < k\) 的。我们用 \(Q_1\) 和 \(Q_2\) 来表示这两类询问。

对于 \(Q_1\) 中的询问，我们显然可以在 \([l, mid]\) 这一范围中求得答案。换句话说，\([l, r]\) 中的第 \(k\) 小即 \([l, mid]\) 中的第 \(k\) 小；而对于 \(Q_2\) 中的询问，我们便可以得知答案坐落于 \((mid, r]\) 这一范围中。显然，求 \([l, r]\) 中的第 \(k\) 小等价于求 \((mid, r]\) 中的第 \(k - cnt\) 小（我们需要剔除 \([l, mid)\) 中的数）。通过这种方式，我们可以把问题 \(Q\) 拆分成 \(Q_1\) 和 \(Q_2\) 两个子问题然后对它们进行分治并递归求解。递归结束于 \(l = r\)，记此时的询问集为 \(Q'\)，则 \(Q'\) 中的所有询问的答案即为 \(r\)，便可以求解问题了。

我们最后需要解决的问题便是如何求得 \(cnt\) 了。我们可以考虑将原始数列中的数值离散化，然后用一个树状数组来维护这一信息。树状数组的第 \(i\) 位表示数列中第 \(i\) 位上的值是否坐落于 \([l, mid]\) 范围内，因此我们只需要在树状数组上求\([L, R]\) 区间的区间和便可以得知下标 \([L, R]\) 间有多少个数坐落于 \([l, mid]\) 范围内，即 \(cnt\)。

具体实现时，我们可以在记录数列中每个数的原始下标后对数列按数值从小到大排序。我们可以通过二分搜索快速查找到 \(l\) 的位置，接下来我们便可以轻松地对于 \([l, mid]\) 中的每个值更新树状数组中的信息。再求得 \(cnt\) 后我们再逐一撤销我们方才对树状数组进行的更改以为接下来递归中求 \(cnt\) 做准备。需要注意的是，撤销更改时不可以直接用 memset，若是如此每一次预处理就与原数组长度有关而并非与当前二分区间有关了，而这会导致复杂度的变化（下面会给出详细说明）。显然，这一过程复杂度是 \(\mathcal{O}(m\log{n})\) 的，其中 \(m\) 是当前二分区间的长度。总的复杂度是 \(\mathcal{O}(n\log^2{n})\) 级别的（下面也会给出详细说明）。

最后附上 我的代码 以供参考。

对于复杂度，这里引用《浅谈数据结构题的几个非经典解法》一文中的相关证明：

定义 \(T(C, S)\) 表示当前待二分区间长度为 \(C\)，待二分序列长度为 \(S\)，且记对于长度为 \(m\) 的序列单次处理复杂度为 \(\mathcal{O}(f(m))\)，则在 \(\mathcal{O}(f(n)) \ge n\) 的前提下有：

\[ T(C, S) = T(\frac{C}{2}, S') + T(\frac{C}{2}, S - S') + \mathcal{O}(f(S)) \]

解得：

\[ T(C, S) \le \mathcal{O}(f(n)\log{n}) \]

而如果每一次处理的复杂度都与序列长度 \(n\) 有关，则有：

\[ T(C, S) = T(\frac{C}{2}, S') + T(\frac{C}{2}, S - S') + \mathcal{O}(n) \]

解得：

\[ T(C, S) = \mathcal{O}(nS) \]

不难发现，这样一来实际上复杂度就变得与暴力没什么区别了……

那么对于这一例题中我们的做法，我们先对数值进行排序，然后在二分查找过程中我们每次直接通过二分查找来确定端点位置，其复杂的是 \(\mathcal{O(m\log{m})}\) 的，其中 \(m\) 为当前处理区间长度。总的复杂度即 \(\mathcal{O}((n + Q) \log{n}\log{C})\)，在该题数据范围下就是 \(\mathcal{O}(n\log^2{n})\) 级别的。

由上面的例子，我们可以初步窥见整体二分适用的问题范围。首先最基本的是，询问的答案必须具有可二分性，并且题目允许离线算法。

其次，我们注意到在上例中二分时我们每一次预处理只与当前区间长度有关。这是因为其余部分对答案的贡献是固定的。具体地阐述，假设我们计算某询问区间内的第 \(k\) 大时，假设该区间内数值的范围为 \([L, R]\)，当我们正在二分数值区间 \([l, r]\) 时，\([l, r]\) 以外的数值区间（即 \([L, l)\) 和 \((r, R]\)）对答案的贡献是固定不变的（询问区间内数值在这些区间内的数的个数固定），因此我们没有必要去重复计算那两个区间对答案的贡献，直接加上即可。由此，贡献也应当是可加的，并且满足交换律和结合律。

那么，如果我们需要支持的操作不仅仅有询问，同时还要有修改呢？事实上，只要加入修改操作后我们依然能够做到二分时每一次预处理只与当前区间长度有关，我们就可以继续使用整体二分。

动态区间第 \(k\) 小

对于一个长度为 \(n\) 的数列，现有两类共 \(q\) 次操作：

• 将第 \(i\) 个数的值修改为 \(v\)；
• 询问第 \(l\) 个数和第 \(r\) 个数之间第 \(k\) 小的数值。

数据范围：\(1 \le n \le 5 \times 10^4, \ 1 \le q \le 10^4\)

题目链接： ZJU 2112: Dynamic Rankings

本题与上一例唯一的区别便在于新加入了修改操作，这样一来上例中的询问集 \(Q\) 在本题中就变成可以含有询问即修改两种操作的操作集了。我们不妨把每个修改操作拆成两步：先删除该位置上原值，再在该位置上插入新值。同时，序列的初始化也可看作 \(n\) 次在位置 \(i\) 插入新值。

我们注意到每一次修改操作其实对答案的贡献是独立的。具体地说，假设二分过程中当前某区间值域为 \([L, R]\)，当前二分区间为 \([l, r]\)。我们若是将该区间内某位置上的值由 \(a_i\) 改变为 \(a_i' \ (l \le a_i' \le r)\) ，并不会改变 \([l, r]\) 以外的区间（即 \([L, l)\) 和 \((r, R]\) 这两个区间对答案的贡献。 由此，每一次预处理的复杂度依然仅仅是与当前二分区间有关的，可以使用整体二分。

故我们依然采用与上例类似的思路对所有操作进行二分。不同之处在于，由于修改这一操作的引入，我们不能随意改变操作的顺序。因此，区别仅仅在于求 \(cnt\) 这一过程的实现。我们不能再像之前一样先对值排序然后二分，因为那样会改变操作的顺序。对于 \(Q\) 内的操作，我们必须按照原顺序进行遍历，查询和修改同时进行（若操作为修改，只应用值在 \([l, mid]\) 区间之内的）。另外在将 \(Q\) 分类为 \(Q_1\) 和 \(Q_2\) 时也要单独开两个单独的空间来进行分类以防止改变操作之间的顺序。

最后附上 我的代码 以供参考。