• 周五. 8月 19th, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

分治 笔记

admin

11月 28, 2021

分治 笔记

分治是我们耳熟能详的算法,在普及组阶段就已经接触到了它。但是当时通常只是随便提一句(我当时是真没做过几个例题),而且通常还有线性的做法把它吊打,我在初学时,很少用到这个东西。

现在水平稍微有了提高,对它的认识改变太多了。

分治?我会!

分治?…我不会

最naive的分治:序列切两半

手上没有现有的例题,就胡一道弱智题吧

给一个序列,求最大连续子序列。换句话说,对于所有的区间,求一个区间和最大的。

“所有的区间” 有 (n^2) 个,不好处理;我们考虑把它 分类 处理

对于我们手上的序列,我们啪的一下把它切两半。所有区间被分成三类,都在左边的,都在右边的,跨区的。对于分治的问题来说,通常都难在处理跨区的情况。

伏笔:这个“区”的含义很广泛,我可没说过是特指序列上的一段嗷

不过这个题很傻逼,左边一半搞一个前缀和,右边一半搞一个前缀和,两边都找最大的那个,加起来,很快啊,做完了!

…做完了?

我们更加深入的思考这个题背后的道理。对于不好处理的问题,我们把它分成小块,然后再合并。其中,分成的子问题,与“合并”这个问题,都比原问题看起来好处理。

这个题看起来很简单,但是可以进一步扩展:

  1. “原问题” 是什么?在什么结构上考虑?(一定是序列?)

  2. 怎么分小块?分几块,多大?(一定对半分?)

  3. 怎么合并?为什么合并更好处理?合并的时候比原问题 多了哪些性质

一种变化:切矩形

大致属于上面的①类变化,③的变化不明显:基本都是处理每个点到分割点的某个信息,然后合并

例题:[ZJOI2016]旅行者

我们要处理网格上的最短路。

网格上的最短路,绕路的方法很多。但是,二者之间的 (x)(y) 坐标若有相差,则无论怎么走,都必然会 跨过 中间的若干行,若干列。

对于 跨过,我们可以想到分治。

一种理解:分治其实是把”跨过”反过来考虑,如果你必然要跨过某个位置,那我给你来一刀,再看看谁不能走了,从而反过来知道,谁要跨过哪。然后就可以计算贡献等。

另:套路:看到网格图上询问/求和/计数,而且数据范围限在 面积 上,可以考虑分治

首先我们可以考虑,找个地方啪的切一刀,然后考虑:假设最短路一定要经过这一条,答案会是多少?

如果一定经过这条分界线,则一定是先到达它一侧边界上某个点,走到另一侧边界上某个点,再继续走。

那我们可以对于两侧边界上的点,分别处理它们到对应侧每个点的最短路。查询的时候把两段最短路拼起来就行了。而对于在两侧内部走的,递归解决即可。

我们肯定把刀切在中间,但是切在行还是列上呢?直观上感觉,把长的切短了比较优。理论一点,设当前矩阵 (n)(m) 列,(T(n,m)) 表示其复杂度。

若横着切,处理最短路的复杂度是 (O(m imes nm)),分治的复杂度是 (2T(n/2,m))

若竖着切,处理最短路的复杂度是 (O(n imes nm)),分治的复杂度是 (2T(n,m/2))

我们发现这个面积每次减少一半。而两种方法,我们肯定取复杂度小的那个切。

设面积为 (S),复杂度为 (T(S)=2T(S/2)+S imes min(n,m))

仔细一想,这个 (min(n,m)le sqrt{S})!于是我们这一部分的复杂度就对了,是 (O(Ssqrt{S}log S))

那我们的 (q) 呢?我们在分治的时候搞个小 trick,就是把询问也分个组,分成仅在左边和仅在右边的。每次把询问的那个数组重排一下然后记个 (l,r) 就行。

这样,我们考虑一个询问,它会在某次分治到边界的时候被完全的处理好。从“分治开始“到”分治到边界”,中间最多经历 (log) 步。所以处理询问的总复杂度是 (O(qlog S))

我们发现这两部分复杂度都非常优秀,好,过了!

还能再变?

例题2:同样是网格图,边权都变成 (1),但是多了障碍。障碍数最多 (20) 个,面积 (le 1e5) ,求两两非障碍点之间的最短路和。

套路:看到 “求所有(区间/路径…)的…的和/积/max/min/…”,大概率是个分治

由这个套路,考虑分治。

我们发现障碍最多才 (20) 个,而面积是 (1e5),那应该会有一大片的空白。

考虑在两个全是空白的行之间,切开一刀。对于跨两边的点,最短路可能不唯一,我们并不能确定具体经过了哪一条。但是我们可以肯定,一定经过了其中的一条,因为绕路显然亏。

于是我们把这一堆边的贡献 合在一起算,就是一边的空白数乘另一边的空白数。

然后我们算完贡献,这些边 相当于没了。我们直接把两行空白并作一行,到最后,顶多是 (41 imes 41) 的一个矩阵。暴力跑最短路!然后就没了

复杂度:(O(S+k^4))

注:这个题尽管也被我认为是“分治”,它并不一定用递归实现

那我为啥说它是“分治”?因为我认为,它的思想方法和分治是相通的,考虑把东西分开计算,然后处理一下跨区的情况。

其实最后那个暴力跑的最短路,可以认为是不断的分分分,最后浓缩成的东西

还能再变:切树(点分治)

即,点分治与边分治。这个没人不会吧,不会吧不会吧

这个可以说是 ①② 变化都有吧。以点分治为例,相比序列上的分治,它是在树上做,每次找重心,并把子树看成小块的子问题去做下去,合并的时候采用树上的套路合并,和序列上也有很多不同。

③的变化也不多,它也可以算是,处理每个点到分割点(重心)的某种信息,然后来合并。当然,也有一些合并方法是树上独有的,比如把已经算过的子树信息放一块,和新加的子树合并。

update 2021.08.11 新增环节:关于实现

点分治的实现有两种形式,一种是,对于当前的根,我们枚举一个子树,算它和以前子树的贡献,然后把这个子树的信息合并到“以前子树”当中

另一种是,我们把所有子树并起来,两两任意组合求答案,减去子树内部两两组合的答案,就是跨过根的答案。这种在一些场合中比上一种好写很多,就是要注意处理一下每个点到根的那条路。

由于边分治的题并不多,而且多数比较毒瘤,这里主要讲点分

经典例题:对于每个 (k),求树上有多少条路径长度 (=k)

点分治后相当于数多少条路径经过根且长度 (=k)。很好做,就把每个子树里的 (dep) 数组看成 (GF),然后卷积一下就行了。我们不讲这里的细节,而是关注于这样做背后的道理。

对于树上的路径的条件计数/带权求和,(没学过点分治的)新手通常会认为它们很难下手:我咋确定一条路径啊?我不肯定得枚举俩端点么?

而点分治的妙处在于,它用根来确定路径,具有优秀的性质;而且它每次找重心,剩下每个子树最多占一半,保证了复杂度是 (log) 的 —— 这样做的前提是树的父子关系不影响答案。

它的分类思想,相当于是按路径经过的点来分类。而点分治问题通常难在如何合并,而“分”的方法,多数情况下变数不多,一个板子粘一下,其它东西,稍 微,调整一下,就能做很多题。

THUSC2021考场上傻逼点分治没打出来的人是谁啊?还搁着说呢

不一样的序列分治:我不算

一般的分治,我们写 (f(l,r)) 表示 ([l,r]) 的答案

这样的分治,我们写 (f(l,r)) 表示,不算 ([l,r]) 的答案。

对于这样的分治,我们可以加入 ([l,mid]) 的贡献,然后算 (f(mid+1,r));然后通过撤销操作(或者直接记录原来的状态,还原回去),加入 ([mid+1,r]) 的贡献之后,算 (f(l,mid))

这样可以做:对于每个位置,计算 去掉 单独一个位置的答案。这也是一个经典trick,很多题目都会用。

一个经典例题:给一个无向图的邻接矩阵,计算:对于每个点,把它删除之后,所有点两两的 (d(x,y)) 之和 。(d(x,y)) 定义为:若存在 (x)(y) 的路径,则它等于最短路,否则它等于 (-1)​。

这里 提交

这很好做:若要加入一段区间的贡献,就枚举两个点,像floyd一样更新最短路就行了。当我们做到分治的边界,(f(l,l)) 的时候,得到的就是 (l)​ 位置的答案。

复杂度:若当前区间长度为 (m)(T(m)=2T(m/2)+n^2m)​。总的复杂度为 (T(n)=O(n^3log n))

不一样的序列分治:我不对半分

很明显这个是 ② 变化,有时也有 ③ 变化

例题:CF1416C

套路:看到异或果断按位

嗯这个题跟异或有关,那么:我们按位!

考虑二进制数的比较过程:从高到低按位比,如果已经分出胜负就直接停止,否则才看下一位

那我们一位一位的看,如果两个数在这一位上已经不同了,那异或上同一个数,肯定还不同。而如果是相同的,那跟这一位就一点关系都没有了:异或上同一个数,还是一样的,比较不出来。

那我们就在这一位上看,假设我异或 (0,1),会有多少逆序对,取小的那个

然后我们要对后面的位继续做:那好办!我们把这一位是 (0) 的都凑到一块,是 (1) 的都凑到一块(重排列)(这样对因为我们已经算完了贡献,随便搞都不影响了),然后对两块分治,每一位都加一下,就得到了最小的总数。

trick: 在二进制数上,有一种分治方法:按照这一位上的数是0还是1,分开处理,再考虑 0/1 之间的贡献

另:整体二分

整体二分也算是这样的“非对半分治”。我们把所有询问里的二分放到一块,(>mid) 的分一类,(le mid) 的分一类,分治。它相当于,按照答案分治

例题略,网上一堆

总结:如果做分治,不要局限于”对半分“,要结合实际情况与性质,搞一个适合本题的分治

更神秘的分治:在答案上分

不知道是哪种变化了,因为我们甚至不切分原问题了

当然,答案区间上的分治多数时候不是独立的,是又要切原问题,又要切答案的

通常会有这样的长相:calc(l,r,L,R) 表示,处理区间 (l,r),答案范围在 (L,R)

有点像整体二分,但我们不一定通过取 (frac{L+R}{2}) 然后检验来缩小区间

例题:CF1039D

我们注意到,随着 (k) 的增加,能选的肯定越来越小,所以具有单调性;

而且显然,(ans_kle n/k),由整除分块的结论,它顶多有 (O(sqrt{n})) 种不同的值。

又知道,对于给定的 (k),有很简单的贪心可以 (O(n)) 求答案:从深到浅,能合并尽量合并

然后我们考虑:calc(l,r,L,R) ,意义如上。

如果 (L=R),那 ([l,r]) 的答案都是这个数;否则我们取 (l,r) 中点,暴力算,通过它来确定两边的范围

一个重要问题是,我们会暴力算多少次?

上面提到,答案区间顶多有 (O(sqrt{n})) 种不同的值,每次取中间的值,两边分开,相当于把它放到线段树上搞。只会有 (log) 层,每层都是 (sqrt{n}),所以只会算 (sqrt{n} imes log n) 次。乘以一次的复杂度 (O(n)),得到总复杂度是

(O(nsqrt{n}log n))

总结:我们的分治,不一定只看原问题,也可以从答案的角度出发,研究答案的性质,并对其分治

线段树分治

线段树本身就是一个相当于把分治记了下来的结构。很多分治的问题可以通过线段树来放到区间上,比如求区间的最大独立集,区间最大连续子段和…它本身就和分治有着很大关系,当然也很适合分治

就好比dp的本质,很适合用来dp!

常见的如非强制在线的动态图连通性,我们可以把每个边存活的时间放在线段树上,然后利用线段树的结构查询一个类似”前缀和”的东西(其实是,“前缀边集并”)

它相当于是利用线段树的结构进行的分治过程

cdq分治

这是一种运用广泛的分治技巧,据说是cdq姐姐提出的,因此在网上被称为“cdq分治”

它的分治思想是:对于当前区间,先算其中一半,然后计算这一部分区间(值已经有了)对另一部分区间的贡献,然后再算另一半区间。

如下是一些经典题

二维LIS

发表回复

您的电子邮箱地址不会被公开。