写在前面

分治作为OI和ACM的基础思路之一以及重要算法
在不同程度不同难度的比赛中都有所提及
这篇文章作为Michael_Bryant的第一篇复活讲义
将由易到难的提供一些分治的想法和一些板子
本文将持续更新 随Michael_Bryant的知识点复习进度

二分

提到分治 相信很多人瞬间就想到了二分 甚至可能只能想到二分
虽说只想到二分并不可取

二分的基础

刚提到二分应该是在数学里面 有个知识点叫做二分法求函数的零点
会的话建议跳过这里 如果不会的话。。。我也不是很想写那就看这里吧
在定义域内选取两点,一点带入函数使得函数值大于0,一点带入函数使得函数值小于0,取两点的中点带入函数,判断函数值大于0还是小于0,如果小于0,则用中点代替使得函数值小于0的点,如果大于0,则用中点代替使得函数值大于0的点,一次类推下去,就可找到零点或者与零点误差很小的点

对于区间[a,b]上连续不断且$f(a)·f(b)\leq 0$的函数$y=f(x)$,通过不断地把函数$f(x)$的零点所在的区间一分为二,使区间的两个端点逐步逼近零点,进而得到零点近似值的方法。
——摘自百度百科
这么说的话感觉还是挺清晰的 这样的话直接上题

二分例题1

代码

二分答案

二分答案要是形容用处在哪里的话
就是这题读完 要是给我一个答案的数值我能马上验证它是不是成立
这样的话不妨考虑二分答案
二分答案对于题目的要求是决策单调
具体的讲 就是当$k$可以的时候$k-1$或者$k+1$一定可以
反之同理
说到这里 上题

二分例题2

题解

这道题就是去二分最后的答案
然后用$s[i] * c[i]- mid * s[i]$作为关键字排序取前$n-k$个判断它们的和是否$ \geq 0$即可

代码

代码放C语言应该不会有人打我吧

二分查找

直接看题

这种题如果数据范围较小的话我们就可以用$ vis[i]=1 $表示$ i $出现过 同理用$ vis[i]=0 $的时候表示$ i $没出现过
但是这道题的数据范围给到了$ 10^{9} $
所以我们按照数的大小排序进行编号 然后对于编号做上面的那种事情就可以啦 非常简单
这里面$num[i]$数组表示的是编号为$i$的数本来是多少

二分查找的应用

八数码问题(逃
在八数码问题中我们利用将整个表格写成一个$9$位数来进行查重 查重的方法可以写$Kantor$展开也可以写二分查找
代码什么的不粘了

三分

说到这里 我们的分治专题第一次迎来了一个难的知识点
我们类比前文二分的基础来理解
二分说的是在一个单调函数中我们通过每次缩小一半的区间来最后得到我们的答案
但是 但是 但是
如果函数不单调怎么办
比如我想找一个二次函数的最小值
这个时候我们二分的话就是这个样子的

这个时候我们并不能知道最小值在左右哪个区间
这时候我们请出三分法

这个时候我们看出来 两个区间的断点$m_1$和$m_2$ 它们的函数值大小和距离极值点的距离是有关系的 主要看的是抛物线的开口方向
比如在这张图中$m_2$的函数值比$m_1$的函数值要小 又因为我们要的是极小值 这样的话我们就可以大胆抛弃$[l,m_1]$这个区间
下图的情况也是同理的

讲到这里的话三分法还是还蛮简单的
上题

三分例题1


这道题其实还挺良心的 给了函数图形
不然的话我们可能还需要画个草图啥的 看看函数单调性啊之类的
然后就是虽然这个函数图象不具有对称性
但是上述的三分规律还是显然成立的
读者可以自行验证

代码

这边代码中用了$3.1$而并非$3$ 原因是防止二次函数这种完全对称的导致两侧函数值相等
(但是好像没什么事情)

三分例题2

传送门
一个显然的策略是我们找到$AB$与$CD$上面的各一个点 然后去算这两个点对应的答案
那么找这个点的感觉有点像二分答案 但是很遗憾 这道题的策略并不单调
所以我们三分这个点就好啦

代码

分治

分治 顾名思义 分 而治之
就是说我们把一个大问题分成很多的小问题来做
然后在某种特定的小问题下我们可以瞬间得到答案
大概这样子 直接上实例吧

归并排序

归并排序可能是$C++$里面最不常用的算法了(可能让用$qsort$的$C$语言也是吧 但是笔者的$C$语言作业不让用 哭哭
归并排序通常用来求一个数列的逆序对个数
逆序对:$1 \leq i < j \leq n,a_i > a_j$
归并排序是分治的最典型的应用
我们通过将数列分为左右两侧 再将两侧的有序的数进行合并 从而达到对数组排序的目的

大致的算法流程如图
计算逆序对也只是在合并过程中 前半段的数比后半段的大 则形成逆序对
直接上代码

分治的其他例题1

最大连续和 传送门
这道题我们就可以进行分治
对于一个区间$ [l,r] $ 显然这个区间的最大连续和出现在左区间内 或者是右区间内 或者左右区间的交点处
所以我们维护每个点的向左最大 向右最大
具体的维护方法是 合并时 区间最左侧的数向右最大是
$max(左区间向右最大,左区间和+右区间向右最大)$
然后分治做就行了

代码

放$C$语言了

分治的其他例题2


题意:给定区间 两种操作 区间$-1$和单点变为$0$ 求让所有数变为$0$的最少次数
一个显然的策略是对大区间进行区间$-1$变成多个小区间 然后对小区间进行第二种操作
所以我们每次找到区间最小值 然后以最小值中间的部分作为我们的小区间进行分治
验证就是小区间答案和$+$最小值和大区间的长度进行比较
时间复杂度$O(n^2)$

代码

以上是Michael_Bryant对于分治基础类别的复习
接下来将更新分治有关算法

分治相关算法

点分治

第一个算法本来准备给CDQ分治的 但是正巧最近在弄图论 所以就给了点分治
点分治是什么呢 顾名思义是对点进行分治 考虑在一棵树上面 我们想维护点对之间的信息
显然我们可以通过暴力枚举的方式来处理 处理方式包括但不限于LCA啊之类的
但是一旦这个数据范围到达了$ 10^5 $以后显然我们就应该寻找方法了
回忆上面提到的 对于一个序列 当我们没什么头绪的时候 我们考虑把这个序列分成几部分然后进行答案的合并
类似的 我们考虑将一个树分成一些树进行分部分的统计问题
具体就是我们统计树根的影响 然后我们依次统计每棵子树的影响
那么这个树根怎么选取呢 我们要选取树的重心 这样子树中最大的就是最小的 使得整体的平均复杂度得到降低
算法流程:
1.找树的重心
2.统计重心的答案
3.点分治
4.统计子树
OK 上题

点分治例题1——luogu模板题

传送门
题目大意是说找寻树上点之间距离为$k$的点对是否存在
直接点分治
考虑对于一个子树内部的点 我们用一个数组存当前存在的到子树重心的距离 然后新加入的点我们用$k$减去这个点到重心的距离 检验这个值之前是否被存储 就可以了

代码

题目拓展

如果题中问满足路径长度等于$k$的路径有几条的话
我们就将当前已有的路径长度进行排序
然后对于新加入的节点 采用二分查找的方式找出加和为$k$的对应区间 那么答案的改变量就是这段区间的长度

代码

在这篇代码中体现出点分治一个经典思路就是
当我们考虑重心的影响的时候 我们可以用整棵树的点对影响减去每棵子树内的点对影响
至于上一篇为什么没用
则是因为我在处理的时候用了两个点到重心的距离和 显然这个影响之和重心有关 不涉及容斥
两种其实都是很好的思路
(明显第二种更好写啊喂)
第一种还要存储已有的路径长度 还要注意清空 还要注意清空别TLE

点分治例题2——聪聪可可

传送门
题意:求路径长度被三整除的点对数的比例
这题显然还是可以用到上述的两种思想
第一种是判断整棵树 再减去每棵子树内部的贡献
第二种就是两个点到重心的路径和
我选择了第一种(可能第二种也会更新一次?毕竟手生
我们考虑点对路径被$3$整除的前提就是一段余$2$一段余$1$ 或者是都整除
我们只需要在这过程中维护这三种余数对应的路径条数就可以了

代码