三大实用的分治算法

· · 算法·理论

点分治

适用于统计路径、点对问题：

核心思想：以当前子树的重心作为当前节点，将该子树内路径分为两类：

在重心处统计答案可能会有不合法（如同一子树两个点，先过来重心再原路返回），考虑容斥，先算总的，再算每棵子树独立的，相减即可。

时间复杂度一般 O(n\log^2n)。

P3806 【模板】点分治 1

先将所有询问离线下来，并一次点分治计算出所有可能出现的距离，判断是否出现即可。

时间复杂度 O(nm\log n)。

计算经过重心路径策略：用先前的路径长度与当前的路径长度判断完后，再加入当前路径长度，不重不漏。

Submission

P4178 Tree

进行一次点分治即可。O(n \log^2 n)。

经过重心路径策略：先统计所有距离的组合方案，再减去每一棵子树内部的组合方案。

Submission

CDQ 分治

适用于解决三维偏序问题（或转化为）。

核心思想：一维排序，二维归并，三维树状数组。

二维偏序有两种解法：对 a 排序后，对 b 树状数组或归并排序。在归并排序法中，假设当前排序区间 [l,r]，且 i<j,b_i \le b_j，则 b_{[l,i]} \le b_j，直接双指针计算这个最大的 i 即可计算贡献。树状数组则直接用下标表示值域，前缀和表示不超过当前数的个数。

在三维偏序中，则是将这两种思想结合起来。对 b 归并排序过程中，找到了这个 i 后，就可以查询 c_j 的贡献了，否则当前的 c_i 要更新树状数组（因为后面计算贡献要用到）。

P3810 【模板】三维偏序（陌上花开）

思路基本同上，对于完全相同的元素，要去重为一个，并记录出现次数 v，更新树状数组时要用出现次数更新，最后计算每个元素的答案时要加上 v-1，统计答案出现次数时应加上 v。O(n \log^2 n )。

Submission

P4093 [HEOI2016/TJOI2016] 序列

记第 i 个位置原本 a_i，最小 mi_i，最大 mx_i，则能转移的前提是 j \le i,mx_j\le a_i,a_j\le mi_i。发现这是个三位偏序的形式，直接 CDQ 分治即可。树状数组存储最大值。

Submission

P2487 [SDOI2011] 拦截导弹

显然 j<i,a_j<a_i,b_j<b_i 时才能转移。最大的长度是经典的 dp，处理方法基本同上一问。接下来考虑如何求概率。

设当前点为结尾最长不上升子序列长度 f1_i，以当前点为开头最长不上升子序列长度为 f2_i。当 f1_i+f2_i-1（i 算重）为答案时，说明 i 有可能被选到。总方案数为 f1_i=ans 的 g1_i 的和，当前为 g1_i \times g2_i，做除法即可。f1 直接求，f2 将序列反转后求最长不下降。g 为最大值的方案数，在更新树状数组时同时维护即可。

注意记录出现次数的变量都要开 double。

Submission

整体二分

P2617 Dynamic Rankings

除了树套树做法外，整体二分也是可以的。

整体二分的主要思想是：通过对值域进行一次二分，来求多个区间排名，从而替代了树套树中的权值线段树。具体地，我们把所有操作按时间先后顺序确定后，假设当前的值域中点为 mid，那么按原顺序进行所有修改值不超过 mid 的操作，用对应的下标更新树状数组。同时对于中间穿插的查询操作，利用树状数组求出 [l,r] 内不超过 mid 的数的个数，再与 k 比较决定答案在 mid 的哪侧，递归下去即可。当值域缩小为一个数时，此时包含的查询的答案即为这个数。

一些注意点：

离散化后，由于最多有 n+m 个不同的数，因此递归最多 \log_2(n+m) 层，总操作数 n+m，每层执行所有操作时间复杂度 O((n+m) \log (n+m) )，总时间复杂度 O((n+m)\log^2(n+m))，实际最大点不到 300ms。（当然不离散化也可以）

Submission

P1527 [国家集训队] 矩阵乘法

基本同上题，同样二分值域，只不过变成了用二维树状数组维护。

Submission