专栏文章

三大实用的分治算法

FFormulaOne
算法·理论参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@miqgaluc
此快照首次捕获于
2025/12/04 04:19
3 个月前
此快照最后确认于
2025/12/04 04:19
3 个月前
查看原文

点分治

适用于统计路径、点对问题：
核心思想：以当前子树的重心作为当前节点，将该子树内路径分为两类：
  • 不经过重心，到子树递归即可
  • 经过重心，直接计算每个点到重心的信息，用双指针等计算答案。
在重心处统计答案可能会有不合法（如同一子树两个点，先过来重心再原路返回），考虑容斥，先算总的，再算每棵子树独立的，相减即可。
时间复杂度一般 O(nlog⁡2n)O(n\log^2n)。

P3806 【模板】点分治 1

先将所有询问离线下来，并一次点分治计算出所有可能出现的距离，判断是否出现即可。
时间复杂度 O(nmlog⁡n)O(nm\log n)。
计算经过重心路径策略：用先前的路径长度与当前的路径长度判断完后，再加入当前路径长度，不重不漏。
Submission

P4178 Tree

进行一次点分治即可。O(nlog⁡2n)O(n \log^2 n)。
经过重心路径策略：先统计所有距离的组合方案，再减去每一棵子树内部的组合方案。
Submission

CDQ 分治

适用于解决三维偏序问题（或转化为）。
核心思想：一维排序，二维归并，三维树状数组。
二维偏序有两种解法：对 aa 排序后，对 bb 树状数组或归并排序。在归并排序法中，假设当前排序区间 [l,r][l,r]，且 i<j,bi≤bji<j,b_i \le b_j，则 b[l,i]≤bjb_{[l,i]} \le b_j，直接双指针计算这个最大的 ii 即可计算贡献。树状数组则直接用下标表示值域，前缀和表示不超过当前数的个数。
在三维偏序中，则是将这两种思想结合起来。对 bb 归并排序过程中，找到了这个 ii 后，就可以查询 cjc_j 的贡献了，否则当前的 cic_i 要更新树状数组（因为后面计算贡献要用到）。

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

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

P4093 [HEOI2016/TJOI2016] 序列

记第 ii 个位置原本 aia_i，最小 miimi_i，最大 mximx_i，则能转移的前提是 j≤i,mxj≤ai,aj≤miij \le i,mx_j\le a_i,a_j\le mi_i。发现这是个三位偏序的形式，直接 CDQ 分治即可。树状数组存储最大值。
  • 应当先递归 [l,mid][l,mid]，后处理 [l,r][l,r] 整体的答案，最后递归 [mid+1,r][mid+1,r]。
  • 用一个数组存储下标，再排序，避免对 aa 数组本身产生影响。
Submission

P2487 [SDOI2011] 拦截导弹

显然 j<i,aj<ai,bj<bij<i,a_j<a_i,b_j<b_i 时才能转移。最大的长度是经典的 dp，处理方法基本同上一问。接下来考虑如何求概率。
设当前点为结尾最长不上升子序列长度 f1if1_i，以当前点为开头最长不上升子序列长度为 f2if2_i。当 f1i+f2i−1f1_i+f2_i-1（ii 算重）为答案时，说明 ii 有可能被选到。总方案数为 f1i=ansf1_i=ans 的 g1ig1_i 的和，当前为 g1i×g2ig1_i \times g2_i，做除法即可。f1f1 直接求，f2f2 将序列反转后求最长不下降。gg 为最大值的方案数，在更新树状数组时同时维护即可。
注意记录出现次数的变量都要开 double。
Submission

整体二分

P2617 Dynamic Rankings

除了树套树做法外，整体二分也是可以的。
整体二分的主要思想是：通过对值域进行一次二分，来求多个区间排名，从而替代了树套树中的权值线段树。具体地，我们把所有操作按时间先后顺序确定后，假设当前的值域中点为 midmid，那么按原顺序进行所有修改值不超过 midmid 的操作，用对应的下标更新树状数组。同时对于中间穿插的查询操作，利用树状数组求出 [l,r][l,r] 内不超过 midmid 的数的个数，再与 kk 比较决定答案在 midmid 的哪侧，递归下去即可。当值域缩小为一个数时，此时包含的查询的答案即为这个数。
一些注意点：
  • 修改操作要分解为删除和插入两步。
  • 初始输入的 aa 应转为 nn 个插入操作。
  • 将操作划分为左右两部分时要按原顺序存储，即时间顺序不能改变。
离散化后，由于最多有 n+mn+m 个不同的数，因此递归最多 log⁡2(n+m)\log_2(n+m) 层，总操作数 n+mn+m，每层执行所有操作时间复杂度 O((n+m)log⁡(n+m))O((n+m) \log (n+m) )，总时间复杂度 O((n+m)log⁡2(n+m))O((n+m)\log^2(n+m))，实际最大点不到 300ms。（当然不离散化也可以）
Submission

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

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

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...