概述
-
纯粹分治是分治思想最纯粹，最朴实，最本质？的应用。
-
我不太会描述...一个典型是平面分治计数。还是看例题吧...
例题
Public NOIP Round #3 数圈圈
-
题意：求一个二维矩阵中的圈的数量。所谓圈，就是字母全部相同的一个矩形壳。
-
数据范围：\(n,m\leqslant 2\times 10^3,6s\)。
-
首先这道题暴力乱搞好像能拿不少分...就是暴力枚举左上角，使用一定的剪枝来枚举长宽。
-
不过我们来谈谈正解吧：二维分治。
-
每次取矩阵较长的一边的中点将其分割开，计算跨分割线的圈数。为什么要取较长的在复杂度分析部分会用到。
-
考虑怎么计算 匚 这种形状的数量，因为两边是对称的，左右分割和上下分割是同构的，所以我们只讨论 匚 的求解：
-
暴力枚举其在分割线上的上界和下界，不妨记其横坐标分别为 \(u,v(u<v)\)，纵坐标为 \(mid\)，这里我们采用 OI 坐标系。
-
整一点悬线法的手法，记 \(U_{x,y},D_{x,y},L_{x,y},R_{x,y}\) 分别为 \((x,y)\) 向上/下/左/右的极大同字母延伸位置（下面使用时可能省略部分下标），于是求的其实是 \(\sum\limits_{i=\max(L_u.y,L_v.y)}^{mid} [D_{u,i}\geqslant v]\)。
-
先考虑 \(L_u.y>L_v.y\) 的情况，此时上式相当于 \(\sum\limits_{i=L_u.y}^{mid} [D_{u,i}\geqslant v]\)，显然我们可以通过在 \(u\) 上开 \(D_{u,i}\) 的桶+预处理后缀和来 \(O(1)\) 地算出上式的值。
-
如果不然，则 \(D\) 变成 \(U\)，其实是对称的。
-
当然后缀和也可以通过树状数组实现，如果把 \((u,i)\) 的影响视为给 \(D_{u,i}\) 上 \(+1\) 的话。因为 \(6s\) 而且 \(n\) 只有 \(2\times 10^3\)，纸面也才 \(4.8\times 10^8\) 的双 \(\log\) 做法也是随便过的。
-
当然，关键是要证明分治本身是 \(O(n^2\log)\) 的。
-
记当前处理的子矩阵短边边长为 \(x\)，长边边长为 \(y\)，则预处理部分的复杂度是 \(O(xy)\)；
-
我们的分割线一定是短边，于是枚举是 \(O(x^2<xy)\) 的。
-
两者合计 \(O(xy)\)，那么可以看出，每层是 \(O(nm)\) 的。于是分治的复杂度是 \(O(n^2\log)\)。
-
-
-
那么其实一共是八种对称的情况，分讨一下就可以了。实现细节较多，但对称性使得相对可调一些。
CF364E Empty Rectangles
-
题意：求一个二维 \(01\) 矩阵中的和为 \(K\) 的矩形数量。
-
数据范围：\(n,m\leqslant 2.5\times 10^3,K\leqslant 6,12s\)。
-
考虑使用二维分治，仍然每次取长边中点划分。考虑怎么求这个东西，我们还是希望枚举其在分割线上的上下端点，求出右边和为 \(x\) 的方案数。
-
注意到这道题好像没有上一道那种优美的“无关性”，\(u,v\) 之间的那些行的影响不容易快速计算...故转而考虑递推，即在已经知道 \(u,v\) 的方案数的情况下，递推出 \(u,v+1\) 的方案数。
-
考虑手模一个样例看看：
-
其中最左边一列即为第 \(mid\) 列。
-
首先考虑 \(u=v=1\) 的情况，此时我们直接暴力扫到左边就行。
-
然后考虑加入第二行的影响。思考实际意义，发现原本向左延伸 \(1,2,3\) 的矩阵和为 \(1,1,2\)，然后现在变成了 \(1,2,3\)。
-
加入第三行，变成 \(2,4,6\)。
-
唔...发现如果把同一列的 \(1\) 垒起来成为一个数，那么它就是和数组的差分数组。看起来有点废话，但这告诉我们，新的 \(1\) 的效果是后缀加...显然可以通过维护差分数组的方式来用树状数组快速求 \(x\) 延伸的矩阵和。
-
但，怎么求矩阵和为 \(x\) 的延伸有多少种呢？
-
仍然考虑这个后缀加。它其实是把从它向右的所有延伸带来的矩阵和都 \(+1\)；\(1\to 2,2\to 3,etc.\)。设加入其之前，其对应位置的和为 \(x\)，则 \(\forall x'>x\)，其改变容易计算；关键是和恰为 \(x\) 的那些延伸有多少变了，有多少没变。
-
考虑暴力！既然 \(K\leqslant 6\)，那么这个“分段函数”的拐点至多有 \(6\) 个。称比左边大的点为拐点，强行记录每个拐点的位置，设插入前为 \(x\)，则相当于在插入处创建一个 \(x+1\) 的拐点，插入处以右的每个拐点对应的值 \(+1\)，\(>6\) 的拐点不必维护，没有价值。
-
那我们来分析一下这个复杂度。发现...发现崩了啊！从 \(u=v=up\) 扫到 \(u=up,v=dw\) 就 \(O(xy)\) 了，这...这...
-
考虑进一步挖掘性质，优化计算。注意到 \(K\leqslant 6\)，扩展行的 \(0\) 对计数无影响，于是事实上我们只需要维护每一行的至多前 \(7\) 个 \(1\) 的位置。预处理扫一遍的复杂度 \(O(xy)\)，从 \(u,v\) 递推到 \(u,v+1\) 的复杂度是 \(O(6\log)\) 左右，相当于 \(O(x^2\log)\)。
-
故总复杂度至少可以分析到 \(O(n^2\log^2)\)，纸面 \(9\times 10^8\)，应该足够过了。
-
上面是我想出来的办法...但显然实现太烦人了。看了题解之后，发现有更妙的办法：
-
我们刚才的所谓拐点，也即 \(sum=x\) 的起始位。我们现在考虑转而维护 \(sum=x\) 的结束位，即定义 \(ri_x\) 表示左边界为 \(u\to v\)，内部和 \(\leqslant x\) 的矩形的右边界最大到哪里。
-
那么显然差分容易求得特定和的方案数，考虑怎么维护这个 \(ri\)，仍然使用递推，每次递推之后仍然按顺序考虑前 \(6\) 个 \(1\)：
-
对于 \(ri_x<pos\) 的：没有影响。
-
\(ri_x\geqslant pos\) 的第一个：\(ri_x=pos-1\)。注意有时候可能 \(ri_x=ri_{x-1}\)，这也许需要一点特判。
-
其他：\(ri_x=ri_{x-1}\)。注意转移顺序。
-
-
啊...是的。要好得多，还没有树状数组的 \(\log\)。这样一来就能把 \(K\) 的常数考虑进来了，不怕被卡常。
UVA1608 不无聊的序列 Non-boring sequences
-
题意：判断 \(S\) 是否 boring。所谓 boring，就是存在 \(S\) 的子串 \(s\) 满足 \(s\) 中不存在只出现一次的元素。
-
数据范围：\(n\leqslant 2\times 10^5\)。
-
注意到若 \(S\) 不 boring，则 \(s_{1\sim n}\) 中必有只出现一次的元素。找到它然后左右区间变成子问题，递归求解即可。
-
注意到若我们每次都从左向右找，则可能构造一个数列 \(112233445678\) 使得我们的复杂度为 \(O(n^2)\)。改为从两边向中间扫，\(T(n)=T(n-x)+T(x)+O(x)(x\leqslant n-x)\)，这个东西的上界是 \(O(n\log n)\)。