分治

Y2y7m · 2023-10-18 00:08:45 · 算法·理论

~~别问我为什么咕咕咕了这么久~~

意义和本质

分治，顾名思义，即是分开后分别处理。对于一个问题直接求取较为困难时，我们可以将其分成多个子问题，每个子问题相对于原本问题数据规模会变小 / 处理起来简单，以至于我们可以在合法时间内求出我们的每一个子问题。在处理出各个子问题后将得到的结果合并以计算出我们的最终问题的答案。

典例1

先来一个经典问题：求取一个序列的最大子段和。

像下面这张图一样，我们将整个序列不断拆成两段（一般是平分），直到拆成的段中只有一个数为止。

显然，一个数的最大子段和就是他自己。

然后我们考虑如何向上合并。

对于一段区间 [l,r]，我们设 mid=\frac{l+r}{2}，若我们已知区间 [l,mid]，[mid+1,r] 的一些信息，是否就可以算出 [l,r] 的最大子段和了呢。

考虑子段的性质：子段是连续的，所以对于区间 [l,r] 中和最大的子段的位置有 3 种情况：

全部在区间 [l,mid] 中
全部在区间 [mid+1,r] 中
一部分在区间 [l,mid] 中，另一部分在区间 [mid+1,r] 中，且在区间 [l,mid] 中的部分是区间 [l,mid] 的一段后缀，在区间 [mid+1,r] 中的部分是区间 [mid+1,r] 的一段前缀。

现在，我们就知道在两个子区间中求什么了：这段区间中的最大子段和，这段区间中和最大的前缀，这段区间中和最大的后缀，这段区间中所有数的和（原因是你也要求出区间 [l,r] 中的和最大的前缀以及和最大的后缀，后面会细说）。

定义一些东西：[l,mid] 为 a，[mid+1,r] 为 b，sum_x 表示为区间 x 中所有数的和，maxpre_x 表示为区间 x 中和最大的前缀，maxsuf_x 为区间 x 中和最大的一段后缀，ans_x 为区间 x 的最大子段和的值。

考虑合并：你发现区间 [l,r] 的答案就是：

ans_{[l,r]}=\max\{ans_a,ans_b,maxsuf_a+maxpre_b\}

考虑到区间 [l,r] 可能还需要向上合并（就是他可能也是一段区间的子区间，我们也要计算出这段区间的一些信息以往上合并）。

所以我们还需要两个式子：

maxpre_{[l,r]}=\max\{maxpre_a,sum_a+maxpre_b\}

maxsuf_{[l,r]}=\max\{maxsuf_a+sum_b,maxsuf_b\}

这样我们一层层往上合并信息就能得出整个序列的最大子段和了。

这样的复杂度是多少呢？

考虑到我们最后一层有 n 个段，所以完全合并完这一层会合并 n 次，然后倒数第二层段数会减半，所以合并 \frac{n}{2} 次，然后倒数第三层是 \frac{n}{4} 次……最终我们将合并次数加和，即为 n。

所以复杂度是 O(n) 的。

典例2

一个经典的分治应用：平面最近点对，给你一个坐标系，在这个坐标系上选出 n 个点，问你其中距离最短的一对点的距离是多少。

先将所有点按 x 排序，x 坐标相同时按 y 坐标排序。

然后开始分治，还是对于一个点区间 [l,r]，假设我们已经分别知道了 [l,mid] 和 [mid+1,r] 的最近点对的距离是多少，我们该如何合并呢？

考虑到我们是按照点 mid 的 x 坐标将这个区间切开的，即所有点中 x 坐标小于等于点 mid 的 x 的点都在左边，其余都在右边。现在我们还不知道左右区间之间的最短距离是多少，考虑到是左区间的一个点和右区间的一个点的最短距离，所以这两个点到直线 x=a_{mid}.x （a_{mid}.x 即为点 mid 的 x 坐标）的距离不能超过已知的最短距离（即已求出的左区间 [l,mid] 和右区间 [mid+1,r] 中的最短距离），所以我们可以将距离这条直线不超过已知的最短距离的点取出排序暴力计算任意两点间距离。

code:

    for(int i=0;i<k;i++)
        for(int j=i+1;j<k&&a[tmp[j]].y-a[tmp[i]].y<d;j++) 
            if(minn>getdis(tmp[i],tmp[j])) d=getdis(tmp[i],tmp[j]);

更多的例题

先看看自己掌握了吗。

魔法GCD Magical GCD

给一个长度为 n（n\le 10^5）的数列 a（a_i\le 10^{12}），找到一个连续子序列使得子序列的公约数与长度的乘积最大，求这个最大值。

还是分开做，对于区间 [l,r]，我们先计算出区间 [l,mid] 和区间 [mid+1,r] 的，然后再计算跨过 mid 的段，每次先固定选出的连续子序列的左端点不动（初始左端点处于 mid，右端点也处于 mid 上（处于 mid 上即为右边区间一个不选）），保持 gcd 固定的情况下尽可能将右端点右移，等到右端点无法移动后再将左端点向左移动一个数，求出新的 gcd，再尽可能向右移动右端点。

相同的，我们还需要固定右端点，保证 gcd 固定时尽可能的向左移动左端点这么计算一次才行。

code：

    int p1=mid,p2=mid,g=a[mid];
    ans=max(ans,g);
    for(int i=p2;i>=l;i--)
    {
        g=gcd(g,a[i]);
        while(p1<r&&g==gcd(g,a[p1+1])) p1++;
        ans=max(ans,(p1-i+1)*g);
    }
    p1=p2=mid;
    g=a[mid];
    for(int i=p1;i<=r;i++)
    {
        g=gcd(g,a[i]);
        while(p2>l&&g==gcd(g,a[p2-1])) p2--;
        ans=max(ans,(i-p2+1)*g);
    }

现在，我们看看分治还能干啥。

当然是：优化dp啦。

可以抽象的认为，如果是普通dp，则是对一个菊花图进行树上dp，而分治后，则是对于一个二叉树进行树上dp（可能不完全对）。

下面来一道题直观的感受一下：

CF1442D Sum

给定 n 个不降的数组。有一个值 ans，初始为 0。你需要进行如下操作 k 次：

选择一个数组，把 ans 加上数组的第一个元素，之后把它删除。

请求出 ans 最大是多少。

所有数组的元素总个数 \leq 10^6，n,k\leq 3000。

你发现这题直接贪心是不可做的，因为我不知道这一轮是拿出哪个元素，可能是这一次能拿出的最大的，也有可能不是最大的，但是拿完这个不是最大的后可以拿这个数所在数组的下一个。

接着，我们想出此题的暴力dp：f_{i,j} 为到了第 i 个序列，已经取出 j 个数的最大和是多少。

转移：

f_{i,j}=\max_{u=0}^{u\leq j,j-u\leq len_i}\{f_{i-1,u}+sum_{i,j-u}\}

其中 sum_{i,j} 为序列 i 前 j 个数的和，len_i 表示序列 i 的长度。

这是 O(n^2k) 的，不行。

然后我们手搓几组样例看看性质。

手搓过后，发现，最多只有一个数组被取过但是没有被取完，其他的要么没动过，要么都取完了。这不难理解，因为数组单调递增，如果我们选了一个数组中的一个，肯定再接着去这个数组中的下一个更优。

这样，我们就可以分治做了，例如我们现在处理到了区间 l,r，如果只选了一部分的数组在这个区间的左半边里，我们就把右半边每个数组当作一个物品做一遍背包，递归左半部分；如果选了一部分的数组在右半部分同理。

CF868F Yet Another Minimization Problem

首先，列出暴力方程：

定义 f_{i,j} 为前 i 个数分成 j 段时的最小价值。

转移为：

f_{i,j}=\min_{k=1}^{i-1}{f_{k-1,j-1}+val_{k,i}}

然后，我们发现这个东西有决策单调性。

接着我们就可以分治优化转移了。

sol(p,l,r,lp,rp) 为现在所在区间是 [l,r]，决策点所在区间是 [lp,rp]，现在已经划分了 p 个区间，每次计算整个 [l,r] 区间中位置 mid 的最优决策点是哪，设其为 from，然后再把决策点区间分成 [lp,from-1]、[from+1,rp]，继续递归下去就可以了。