概述
$\text{CDQ}$ 分治一般用于离线处理一系列操作，这些操作一般包括修改和询问。它通过递归计算子问题、计算两部分的贡献来高效地处理问题。
基本思想
- 我们把操作看做一个序列，用区间 $[l,r]$ 表示。将这个区间 $[l,r]$ 分成两部分 $[l,m],[m+1,r]$。
- 分。递归处理左右区间的操作。
- 治。合并两个子问题，同时考虑左区间 $[l,m]$ 对右区间 $[m+1,r]$ 的贡献。即用左区间帮助解决右区间的问题。
$\text{CDQ}$ 分治和一般分治的主要不同在于：普通分治在合并子问题时，左区间不会对右区间产生影响。
偏序问题
给定一个序列 $a_i$，每个数有 $k$ 个属性，其中第 $i$ 的数的属性为 $(x_{i,1},x_{i,2},\cdots,x_{i,k})$。称 $a_i>a_j$ 当且仅当对于任意整数 $l\in[1,k]$ 都有 $x_{i,l}>x_{j,l}$。求对于序列中的每个元素 $a_i$，比 $a_i$ 小的元素个数。
三维偏序
题目链接：「LOJ 112」三维偏序
我们将每个数的属性用 $(x_i,y_i,z_i)$ 表示。首先把序列按照 $x_i$ 排序，接下来把第二维 $y_i$ 利用 $\text{CDQ}$ 分治递归计算子问题。合并时按照 $y_i$ 归并排序，用树状数组维护 $z_i$，左区间更新右区间的答案即可。注意要及时把树状数组归零。
时间复杂度：$\mathcal O(n\log^2 n)$
四维偏序
题目链接：NULL
比三维多了一维？那么再套一个 $\text{CDQ}$ 不就行了？QAQ
时间复杂度：$\mathcal O(n\log^3 n)$
更高维偏序
题目链接：NULL
对于更更高维的偏序问题，虽然可以继续套 $\text{CDQ}$ 分治，这样的复杂度在渐进意义下是优秀的，但是在 $n$ 比较小的情况下还没有暴力跑得快。
我们可以使用对于每一维，用 $\text{bitset}$ 记录前面比当前数小的元素集合，最后把 $\text{bitset}$ 取个 $\&$ 即可。
使用分块降低复杂度。
时间复杂度：$\mathcal O(kn\sqrt n)$，其中 $k$ 为维数。
总结
对于多维偏序问题、多维数据结构问题，我们可以用一步步降维。例如排序、数据结构、$\text{CDQ}$ 分治等都是降维工具。
我们还可以利用 $\text{CDQ}$ 分治加速动态规划等，具体应用可以参考下方习题。
2 条评论
Orz
$$ \texttt{QwQ} $$