分治学习笔记
分治（英语：Divide and Conquer），字面上的解释是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。
From OI-wiki
主定理
假设有递推关系式 $T(n) = aT(\frac{n}{b}) + f(n)$，其中 $n$ 是问题规模，$a$ 是递推子问题数量，$\frac{n}{b}$ 是每个子问题的规模，$f(n)$ 为递推以外做的工作（例如合并）。
那么有
- 若 $f(n)= O(n^c)$ 且 $c<\log_b a$，则 $T(n)=\Theta(n^{\log_b a})$
- 若 $f(n) = \Theta(n^{\log_b a})$，则 $T(n)=\Theta(n^{\log_b a}\log n)$；
- 若 $f(n) = \Omega(n^c)$ 且 $c>\log_b a$，并且存在一个常数 $k<1$，使得 $af(\frac{n}{b})\le kf(n)$ 对足够大的 $n$ 都成立，则 $T(n)=\Theta(f(n))$。
这里的三个符号简单来说，
$O(f(n))$ 指问题的复杂度不超过 $f(n)$，即 $O$ 规定了问题的上界
$\Omega(f(n))$ 指问题的复杂度不小于 $f(n)$，即 $\Omega$ 规定了问题的下界
而当复杂度同时满足 $O(f(n))$ 和 $\Omega(f(n))$ 时，我们就说问题复杂度满足 $\Theta(f(n))$
注意，在算法竞赛里经常要考虑的是最坏情况，也就是尽量多考虑 $O$
其实主定理可以简单理解：
如果分治外的操作不比 $n^{\log_b(a)}$ 多，那么总的复杂度为 $\Theta(n^{\log_b(a)})$
更进一步地，可以理解为如果分治外的操作比分治操作增速慢，那么就是分治操作占主要复杂度
如果分治外的操作数量级和 $n^{\log_b(a)}$ 相当，那么总复杂度为 $\Theta(n^{\log_b(a)}\log_n)$
这是最常见的情况，如果数量级相当，那么总复杂度还要再乘上 $\log_n$
如果分治外操作数量级不比 $n^{\log_b(a)}$ 小，那么当n很大时，总复杂度会趋向于 $\Theta (f(n))$
也就是说如果分治外的操作非常慢，那么算法就会被这些操作占主导，分治的作用减弱
举个例子，归并排序的递推关系式应为 $T(n) = 2 T(\frac{n}{2}) + \Theta(n)$
那么 $a = b = 2,f(n) = \Theta(n) = \Theta(n^{\log_22})$，故 $T(n) = \Theta(n \log n)$
除此之外还有一种直观的方式
CDQ 分治
一般用来解决多维偏序问题。主要思想就是区间分治，然后计算左边区间对右边区间产生的贡献。
逆序对其实本质上就是一个二维偏序，所以更高维的偏序问题我们都能与逆序对类比。
回想一下，逆序对可以利用归并排序解，同时也可以利用树状数组/权值线段树来解决，这说明了实际上数据结构维护的也是一个偏序关系，并且能动态维护。
例1（三维偏序）：P3810 【模板】三维偏序（陌上花开)
有 $ n $ 个元素，第 $ i $ 个元素有 $ a_i,b_i,c_i $ 三个属性，设 $ f(i) $ 表示满足 $ a_j \leq a_i $ 且 $ b_j \leq b_i $ 且 $ c_j \leq c_i $ 且 $ j \ne i $ 的 $j$ 的数量。
对于 $ d \in [0, n) $，求 $ f(i) = d $ 的数量。
第一维直接当成坐标，我们可以直接进行一个排序在 $\Theta(n \log n)$ 的时间里处理掉。
第二维利用归并排序解决（虽然我去年比较傻逼写了个 sort 导致复杂度多了 $\log$）
第三维就必须要上数据结构了，这里选择好写的树状数组，代码如下
1 | int t[N]; |
数轴上有 $n$ 头牛，每头牛的坐标为 $x_i$，听力为 $v_i$，如果第 $i$ 头和第 $j$ 头奶牛说话，会发出 $\max{v_i,v_j}*|x_i-x_j|$ 的音量
假设每两头奶牛都在互相说话，问总的音量大小
$n,x_i,v_i\leq 2\times 10^4$
我会 $n^2$!!!
这个柿子两边都恶心人，但是我们的直觉告诉我们先把 $v_i$ 排序掉，$\max$ 就都由右边的点提供了。这样就消掉了左边的 $\max$。为什么不消掉绝对值？因为绝对值相对来说好处理很多。
考虑分治，假设我们已经处理完了 $[l,mid]$ 和 $[mid+1,r]$ 的音量大小，那么当一个 $p \in [mid+1,r]$ 计算的时候，所有已经遍历过的左半边的元素 $q$ 必定有 $x_q > x_p$ ，同样，所有没有遍历过的左半边元素 $q’$ 必定有 $x_{q’} < x_p$ 分开计0算即可。
在合并序列的过程中，每加入一个右区间的牛 $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)$，容易用前缀和快速计算。(这段话直接贺了 $\color{black}C\color{red}{utest_Junior}$ blog里的一句话)
代码如下
1 | struct node { |
例3：P1228 地毯填补问题
相传在一个古老的阿拉伯国家里，有一座宫殿。宫殿里有个四四方方的格子迷宫，国王选择驸马的方法非常特殊，也非常简单：公主就站在其中一个方格子上，只要谁能用地毯将除公主站立的地方外的所有地方盖上，美丽漂亮聪慧的公主就是他的人了。公主这一个方格不能用地毯盖住，毯子的形状有所规定，只能有四种选择（如图）：
并且每一方格只能用一层地毯，迷宫的大小为 $2^k\times 2^k$ 的方形。
$k\leq 10$
最开始填一小块肯定是如图
$k = 2$
$k = 3$
做完了
从大到小递归
先把整个大矩形划分为 $4$ 块，找到公主在哪块，然后递归地去填这一块
填完之后，把中间 $2\times 2$ 剩下的 $3$ 个块用一个图形填满，然后递归剩下的3个
由于剩下的 $3$ 个块每块恰好有一个，因此也可以完全套用之前的做法去解决
更进一步地，你可以发现当 $k=1$ 的时候，这个分治策略也是适用的
$2\times 2$的块可以划分为 $4$ 个块，公主在的那一块已经满了，而剩下的 $3$ 块就是其他情况中的，中间 $2\times 2$ 剩下的 $3$ 个块
给定平面上 $n$ 个点，找出其中的一对点的距离，使得在这 $n$ 个点的所有点对中，该距离为所有点对中最小的
$n \leq 2\times 10 ^5 $
考虑分治，首先将点按照 $x$ 进行排序。
假设我们已经处理完 $x$ 范围在 $[l,mid]$ 和 $[mid+1,r]$ 的点的最短距离，实际上只要处理跨过中线 $x = mid$ 的点对距离即可。
首先，对于左边的一个点 $(x,y)$，假设左右两半区间内部的最近点对距离为 $d$
右边的点的坐标范围必须在 $(mid,y-d)$ 到 $(mid+d,y+d)$ 这样一个$d\times 2d$的长方形上
超出这个范围的点距离一定$> d$，否则没有意义
然后易证，在这样一个 $d\times 2d$ 的长方形之内，至多有 $6$ 个点
因为如果超过 $6$ 个点，则无论如何分配点的位置，距离都会小于$d$
因此只需要枚举每一个左边的点，再枚举右边对应方形内的点，就可以把分治外操作复杂度压到 $f(n)=O(n)$
这样用主定理算出来总复杂度就是 $O(n\log n)$
代码
1 | struct poi { |
例5：NOI2007 货币兑换
设 $f[i]$ 为这一天的最大值，那么就有转移方程：
$$
f_i = \max_{j<i} (\frac{f_j}{a_j\times rate_j + b_j} * (rate_j\times a_i +b_i))
$$
这个式子的含义就是对于第 $j$ 天的全部买入，在第 $i$ 天全部卖出。
接下来考虑对式子变形一下：
$$
\frac{f_i}{b_i} = \max(\frac{f_j\times rate_j}{a_j\times rate_j + b_j}\times \frac{a_i}{b_i} + \frac{f_j}{b_j + rate_j\times a_j})
$$
这个式子可以斜率优化，$x = -\frac{f_j\times rate_j}{a_j\times rate_j + b_j},y = \frac{f_j}{b_j + rate_j\times a_j},k = -\frac{a_i}{b_i}$。
答案就是凸包上与斜率为 $k_i$ 相切的点，如果在线做的话需要动态凸包，需要平衡树维护。
所以就有了 CDQ ！
我们把这个东西看作两个操作：加点和求与斜率为 $k$ 的直线相切的点。
将操作序列二分，先求出左边的操作序列的答案，再求左边操作序列得到的凸壳对右边操作序列中询问操作的影响，最后求右边操作序列的答案。
具体来说对于第 $i$ 天的询问，我们只要考虑 $1\to i-1$ 上的加点，那么只需要考虑 $[l,mid]$ 和 $[mid+1,r]$ 的点构成的凸包的解。
那么对于 $[1,i-1]$ 的凸包，其实就是 $[1,mid]$ 和 $[mid+1,i-1]$ 构成的凸包的并。
这部分其实可以直接看 cdq 本人的论文
用 $[1,\frac{n}{2}]$ 的决策来更新 $[\frac{n}{2}+1,n]$ 的$~f[i]$ 值：
类似用平衡树的方法，我们可以对 $[1,\frac{n}{2}]$ 的所有决策建立一个凸线，对$[\frac{n}{2}+1,n]$ 的所有 $i$ 按照 $-\frac{a[i]}{b[i]}$ 从大到小排序，凸线的斜率是单调的，$-\frac{a[i]}{b[i]}$也是单调的，这样我们就可以通过一遍扫描来计算出对于每一个 $i$ 在$[1,\frac{n}{2}]$里面最优的决策 $j$.
现在面临的问题是如何对于一段区间 $[l, r]$ 维护出它的凸线：由于 $f$ 值是临时计算出来的，我们只需要递归的时候利用归并排序将每一段按照 $f$ 值从小到大排序，凸线可以临时用一个栈 $O(n)$ 计算得出．
好接下来论文就开始讲天书了，所以自己理解一手。
整个过程实际上就是利用 CDQ 分治来维护下凸壳，这就是一个叫做 CDQ 分治维护斜率优化的思路了。
整体二分
讲课用的是蓝书上的例子，这个比较好理解。
例0：带修改区间第 $k$ 大
利用这个例子来讲解整体二分。
整体二分这个东西的思想就在于，如何在 $\log$ 级别的时间下同时处理多个询问，虽然说是二分，但是实际上已经是分治的过程了。
一般地，我们依然选定 $mid$ 为答案的猜想值。接下来我们对所有询问同时进行一次判定，若答案 $\leq mid$ 那么就分到左边，否则分到右边，递归下去进行分治。当 $l = r$ 时，我们就对当前的所有询问找到了对应的答案。
可以使用整体二分解决的题目需要满足以下性质：
询问的答案具有可二分性
修改对判定答案的贡献互相独立，修改之间互不影响效果
修改如果对判定答案有贡献，则贡献为一确定的与判定标准无关的值
贡献满足交换律，结合律，具有可加性
题目允许使用离线算法
——许昊然《浅谈数据结构题几个非经典解法》
如果带修改呢？比如本题的单点修改，我们把它和查询统一成一类操作，然后一起整体二分即可。
注意：如果一个询问的答案是大于 $k$ 的，则在将其划至右侧前需更新它的 $k$，即，如果当前数列中小于等于 $mid$ 的数有 $t$ 个，则将询问划分后实际是在右区间询问第 $k-t$ 小数。
设查询时间复杂度为 $O(T)$，则总时间复杂度为 $O(T\log ansmax)$
Tips:如果使用 vector 实现的话，会更好写，但是空间会多一点，看具体情况要不要卡常吧。
例1：ZJOI2013 K大数查询
这个题和上面那个题没啥差别，理解了就好写，就是把树状数组换成线段树区间修改就可以了。
例2：Luogu1527 矩阵乘法
把点的操作都拆了，变成有 $n^2$ 个操作，每次在 $(i,j)$ 上加点。
考虑查询，查询 $(x_1,y_1)$ 到 $(x_2,y_2)$ 这个矩阵，那么就差分一下，变成查询 $x1-1$ 之前，$[y_1,y_2]$ 这段和 $x_2$ 之前，$[y_1,y_2]$ 这段相减，得出了这个询问的值。
推荐拓展阅读：
国家集训队论文 2013 浅谈数据结构题的几个非经典解法 许昊然