三大实用的分治算法

· · 算法·理论

点分治

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

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

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

时间复杂度一般 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,统计答案出现次数时应加上 vO(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-1i 算重)为答案时,说明 i 有可能被选到。总方案数为 f1_i=ansg1_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