三大实用的分治算法
点分治
适用于统计路径、点对问题:
核心思想:以当前子树的重心作为当前节点,将该子树内路径分为两类:
- 不经过重心,到子树递归即可
- 经过重心,直接计算每个点到重心的信息,用双指针等计算答案。
在重心处统计答案可能会有不合法(如同一子树两个点,先过来重心再原路返回),考虑容斥,先算总的,再算每棵子树独立的,相减即可。
时间复杂度一般
P3806 【模板】点分治 1
先将所有询问离线下来,并一次点分治计算出所有可能出现的距离,判断是否出现即可。
时间复杂度
计算经过重心路径策略:用先前的路径长度与当前的路径长度判断完后,再加入当前路径长度,不重不漏。
Submission
P4178 Tree
进行一次点分治即可。
经过重心路径策略:先统计所有距离的组合方案,再减去每一棵子树内部的组合方案。
Submission
CDQ 分治
适用于解决三维偏序问题(或转化为)。
核心思想:一维排序,二维归并,三维树状数组。
二维偏序有两种解法:对
在三维偏序中,则是将这两种思想结合起来。对
P3810 【模板】三维偏序(陌上花开)
思路基本同上,对于完全相同的元素,要去重为一个,并记录出现次数
Submission
P4093 [HEOI2016/TJOI2016] 序列
记第
-
应当先递归
[l,mid] ,后处理[l,r] 整体的答案,最后递归[mid+1,r] 。 -
用一个数组存储下标,再排序,避免对
a 数组本身产生影响。
Submission
P2487 [SDOI2011] 拦截导弹
显然
设当前点为结尾最长不上升子序列长度
注意记录出现次数的变量都要开 double。
Submission
整体二分
P2617 Dynamic Rankings
除了树套树做法外,整体二分也是可以的。
整体二分的主要思想是:通过对值域进行一次二分,来求多个区间排名,从而替代了树套树中的权值线段树。具体地,我们把所有操作按时间先后顺序确定后,假设当前的值域中点为
一些注意点:
-
修改操作要分解为删除和插入两步。
-
初始输入的
a 应转为n 个插入操作。 -
将操作划分为左右两部分时要按原顺序存储,即时间顺序不能改变。
离散化后,由于最多有
Submission
P1527 [国家集训队] 矩阵乘法
基本同上题,同样二分值域,只不过变成了用二维树状数组维护。
Submission