分治学习笔记

Cutest_Junior · 2021-07-20 17:56:07 · 个人记录

分治学习笔记

主定理

假设有递归关系式 T(n)=aT(\dfrac{n}{b})+f(n)，其中 n 是问题规模，a 是递推子问题数量，\dfrac{n}{b} 为每个子问题的规模，f(n) 为递归以外做的工作：
1. 如果分治外的操作比 n^{\log_ba} 少，那么总的复杂度为O(n^{\log_ba})，更进一步地，可以理解为如果分治外的操作比分治操作增速慢，那么就是分治操作占主要复杂度；
2. 如果分治外的操作数量级和 n^{\log_ba}相当，那么总复杂度为O(n^{\log_ba}\log n)，这是最常见的情况，如果数量级相当，那么总复杂度还要再乘上 \log n；
3. 如果分治外操作数量级比 n^{\log_ba}大，那么当 n 很大时，总复杂度会趋向于 O(f(n))，也就是说如果分治外的操作非常慢，那么算法就会被这些操作占主导，分治的作用减弱。

cdq 分治

离线算法，常数较小，常用于处理多维偏序的问题。

P3810 三维偏序

曾用动态开点树状数组套动态开点线段树过了。

多维偏序问题通常用 cdq 分治解决；
先按 a 排序，保证合并过程中前半部分不可能在三个指标上都大于等于后半部分的元素，但是要特判一下相同元素；
我的方法是排序后去重，并给每一个元素一个权值 s，表示它在原序列上的出现次数；
在合并的过程中，对 b 做归并排序，就很容易对后半部分每一个元素判断有多少个前半部分的元素满足 a,b 都小于等于它了，至于 c 可以用权值树状数组处理；
具体来说，每加入一个前半部分的元素 i，就在树状数组的 c_i 位置加上 s_i，每加入一个后半部分的元素 j 就查询位置小于等于 c_j 的区间和；
在区间内的元素，肯定满足 a_i\le a_j（初始时排序），肯定满足 b_i\le bj（归并排序），肯定满足 c_i\le c_j（按 c 插入树状数组），综上，被计入答案的一定满足条件；
在区间外而在前半部分中的元素，要么还没插入，则不满足 b_i\le b_j，要么插入了但在区间外，则不满足 c_i<c_j，综上，没被计入答案的一定不满足条件。

P2345 MooFest G

+ 两头牛 $i,j$ 发出的音量是 $\max(v_i,v_j)\times\mid x_i-x_j\mid$； + 公式看起来非常复杂，既有取 $\max$ 的操作，又有绝对值操作，似乎两者都不方便直接运算； + 考虑先对 $v$ 升序排序，然后对 $x$ 进行归并排序（也是默认升序），在合并的过程中维护区间内的音量信息； + 根据归并排序的特性，我们只需要考虑如何合并两个已经计算出音量的区间； + 因为原来按 $v$ 升序排序，所以现在左区间的 $v$ 一定都小于右区间的 $v$，$\max$ 容易维护； + 因为对 $x$ 进行归并排序，所以两个区间内的 $x$ 都是升序序列； + 在合并序列的过程中，每加入一个右区间的牛 $i$，新增的音量为 $v_i\times(\sum\limits_{左区间中满足 x_j<x_i 的 j}x_i-x_j+\sum\limits_{左区间中满足 x_j\ge x_i 的 j}x_j-x_i)$，容易用前缀和快速计算。 ### P1228 地毯填补问题太水了不想记，但是本题还挺考验码力的。 ### P1429 平面最近点对 + 先按 $x$ 排序，然后对 $y$ 归并排序； + 归并排序过程中维护区间最近点对距离 $d$； + 合并时，对于左区间的点 $(x,y)$，可能形成新的最近点对的点一定在左下角为 $(mid,y-d)$，右上角为 $(mid+d,y+d)$ 的矩形内，$mid$ 为左区间最大的 $x$，矩形外要么是左区间的点，已经被考虑过，要么距离一定大于 $d$（横坐标或纵坐标差的绝对值大于 $d$）； + 可以证明区间内点的个数不超过 $6$，实际上远远小于这个数； + 先去掉右区间横坐标大于 $mid+d$ 的点（只是暂时去掉，为了方便计算新的 $d$），左区间一个指针 $i$，从头到尾扫，右区间一个指针 $j$，对于每个 $i$，跳回最小的纵坐标使纵坐标大于等于 $y_i-d$，因为已经去掉横坐标大于 $mid+d$ 的点，所以每次往回跳 $j$ 都不会跳超过 $6$ 个点，每次合并计算新的 $d$ 的复杂度为 $O(kn)$，$k$ 不超过 $6$。