简单普通分治
分治，即将原问题分成一些较小规模的问题分别处理，再合并其结果。
由于分治只是一种思想，具体的解法各不相同，因此将会有较多的例题。
例题 1
题意
给定一个长为 $n$ 的序列 $a$，求其最大子段和。
做法
设计一个函数 solve(l, r) 表示求 $a$ 的第 $l$ 个到第 $r$ 个的最大子段和 $ans$，并返回一些辅助计算的量：区间前缀和的最大值 $lx$，区间后缀和的最大值 $rx$，区间和 $s$。
转移方式：$ans = \max(A _ {ans}, B _ {ans}, A _ {rx} + B _ {lx})$，$lx = \max(A _ {lx}, A _ s + B _ {lx})$，$rx = \max(B _ {rx}, A _ {rx} + B _ s)$，$s = A _ s + B _ s$，其中 $A, B$ 分别是左右两侧递归返回的结果。
其实这样分治中点任意选，时间复杂度都是线性的。
例题 2
题意
给定一个长为 $n$ 的序列 $a$，将其从小到大排序。
做法 1 归并排序
设计一个函数 solve(l, r) 表示将 $a$ 的第 $l$ 个到第 $r$ 个排序后再存入 $a$。
选 $m$ 做 $[l, r]$ 区间的中点，分治下去排序 $[l, m]$ 和 $[m + 1, r]$，随后考虑合并两个排序好的序列。
创建一个新数组 $b$，用两个指针分别扫两边两个排好序的序列，每次将较小的那个放入 $b$ 的最后并将指针后移。最后把 $b$ 这一段复制到 $a$ 即可。
做法 2 快速排序
设计一个函数 solve(l, r) 表示将 $a$ 的第 $l$ 个到第 $r$ 个排序后再存入 $a$。
从区间里随机选择一个数，将小于它的放在左边，等于它的放在中间，大于它的放在右边。分别将左边和右边排序即可。
这样做的期望复杂度是 $O(n \log n)$ 的。
例题 3
题意
给定一个长为 $n$ 的序列 $a$，求其逆序对数，即 $\sum _ {i = 1} ^ n \sum _ {j = 1} ^ {i - 1} [a _ i < a _ j]$（其中 $[P]$ 表示若 $P$ 成立则取值为 $1$，否则取值为 $0$）。
做法
归并排序。
设计一个函数 solve(l, r) 表示将 $a$ 的第 $l$ 个到第 $r$ 个排序后再存入 $a$，同时求出区间内逆序对数。
类似的合并，但是在加入某个元素的时候加上它和另一边的贡献。在以下两种算法中任选一个，就可以做到不重不漏的统计所有逆序对：加入左边数时，加上右边已经加入的数的个数；加入右边数时，加上左边未加入的数的个数。
如果把 $(i, a _ i)$ 看作一个二元组，那么其实这就是一个二维偏序。
例题 4
题意
给定一个长为 $n$ 的序列 $a$，求其第 $k$ 小的数，要求期望线性时间。
做法
设计函数 solve(l, r, k) 表示求出区间 $[l, r]$ 中的第 $k$ 小的数。
类似快速排序的，随机选择一个数并划分。之后可以按照小于它的数的数量和大于它的数的数量判断应该往哪边递归求或者就是当前数。
线段树分治
将一个序列，对于在这个序列上的一些区间，按照线段树的结构来分治。
例题 1
题意
图连通性：维护一个 $n$ 个点的图，支持以下三种操作，操作数为 $q$，可以离线。
- 加入无向边 $(u, v)$
- 删除无向边 $(u, v)$（保证边此时存在）
- 查询 $u, v$ 两点是否连通
$n, q \le 10 ^ 5$
做法
若是没有删除操作，可以直接并查集。
考虑把每条边在时间轴上的出现区间拿出来做线段树分治。
具体的，对时间轴建一个线段树。
算出每条边的出现区间后，在时间轴上将每个区间拆分成线段树上的区间（一共 $O(q\log q)$ 个区间），随后搜索这棵线段树。
搜到某个结点时，加入其上的所有边。离开某个结点时，撤销其上的所有边。搜到叶子结点而其是个询问时就直接查询。
由于有撤销操作的存在，需要并查集不是均摊的，所以必须要按秩合并。
时间复杂度 $O(q\log q\log n)$，空间复杂度 $O(q\log q)$。
整体二分
对于一些单次询问可以二分，但是不能每次都二分的题目，可以使用整体二分。整体二分是对被二分的「值域」做分治，将询问分到两边。
一般是设计函数 solve(l, r, qry)（其中 qry 是一个存储了一些询问的列表）表示已知 qry 里所有询问的答案都在 $[l, r]$ 中，要求出这些询问。
取中点 $m = \lfloor \frac{l + r}{2} \rfloor$，判定询问是否小于等于 $m$，随后分治下去。
例题 1
题意
给定 $n$ 个数的序列，支持 $q$ 次单点修改或查询区间第 $k$ 小，可以离线。
$n, q \le 10 ^ 5$
题目来源：Dynamic Rankings
做法
先离散化出现过的数。
对于每个出现过的数，记录其出现的时间范围 $[tl, tr]$、出现位置 $p$ 和值 $v$，这样就将动态的修改转变为了静态的问题。
询问则是，求出时间包含 $t$，出现位置在 $[l, r]$ 中这些数的第 $k$ 小。
随后直接整体二分。
每次调用 solve(l, r, qry)，将值在 $[l, m]$ 中的数都拿出来，和所有询问做一次二维数点，再将数点结果和询问的 $k$ 相比较，即可得知每个询问的答案在哪一边。
若认为 $n, q$ 同阶，则复杂度为 $O(n \log ^ 2 n)$。
例题 2
题意
有 $n$ 个国家，$m$ 个空间站和 $k$ 次陨石雨。第 $i$ 个空间站属于国家 $o _ i$；第 $i$ 个国家希望收集到 $p _ i$ 单位的陨石；第 $i$ 次陨石雨会使编号在区间 $[l _ i, r _ i]$ 内的空间站各收集到 $a _ i$ 单位的陨石。对于每个国家，求其在第几次陨石雨后收集齐 $p _ i$ 单位陨石。
题目来源：POI 2011 Round 3. Day 2. A「Meteors」
做法
直接整体二分。
即，对于二分区间 $[l, r]$，将修改做到中点 $m$，判断是否达成条件即可。判断完成后，可以先分治 $[m + 1, r]$，随后删除 $[l, m]$ 的修改，分治 $[l, m]$ 即可。
cdq 分治
关于 cdq 分治：目前似乎网络中并没有一个关于 cdq 分治的明确定义，一般理解为在序列上分治时，先处理左侧内部的贡献，随后计算左侧到右侧的贡献，最后再计算右侧到右侧的贡献。
进行完 $[l, r]$ 的分治后，其中要计算的东西都会被算好。 从某种意义上而言，归并排序算逆序对也算 cdq 分治。
例题 1
题意
给定 $n$ 个三元组 $(a _ i, b _ i, c _ i)$，对于每个 $i$ 求出 $\sum\limits _ {j = 1} ^ {n} [a _ j \le a _ i][b _ j \le b _ i][c _ j \le c _ i]$。
$n \le 10 ^ 5$
做法
先将三元组按 $a$ 从小到大排序。设计函数 solve(l, r) 表示计算出区间 $[l, r]$ 内的贡献。
分治后，由于左侧 $a$ 都小于右侧，所以左侧对右侧的贡献就是一个二维偏序的关系，可以使用 cdq 或者树状树组等 ds 解决。
复杂度 $O(n \log ^ 2 n)$。
这就是三维偏序。
例题 2
题意
给定 $n$ 个二元组 $(a _ i, b _ i)$，求其二元最长上升子序列（即要求子序列后一项的 $a$ 和 $b$ 都大于前一项）。
$n \le 10 ^ 5$
做法
考虑 dp：$f _ i$ 表示以 $i$ 结尾的最长上升子序列，转移式为 $f _ i = \max \limits _ {j < i, a _ j < a _ i, b _ j < b _ i} f _ j + 1$。
直接分治，尝试计算 $[l, m]$ 到 $[m + 1, r]$ 的贡献。发现其形式为一个先单点修改，之后再前缀矩形求 $\max$，可以扫描线，或者再次 cdq 分治解决。
例题 3
题意
半在线卷积。
给定序列 $g _ {1, 2, \cdots, n}$，求序列 $f _ {1, 2, \cdots, n}$。其中 $f _ 1 = g _ 1$，$f _ i = \sum\limits _ {j = 1} ^ {i - 1} f _ j g _ {i - j}\ (i > 1)$。
均在模 $998244353$ 意义下进行。
$n \le 10 ^ 5$
做法
直接分治，尝试计算 $[l, m]$ 到 $[m + 1, r]$ 的贡献。即为 $f _ k + \sum\limits _ {i = l} ^ {m} f _ i g _ {k - i} \to f _ k$。
后面那一堆是一个卷积的形式，长度不超过 $r - l + 1$，直接应用快速的卷积算法即可。
例题 4
题意
矩形加矩形求和。
$q$ 次操作，每次可以给一个矩形加上一个值，或者给一个矩形求其中元素的和。
矩形可以很大，$q \le 10 ^ 5$。
做法
直接对询问分治，依旧是只用考虑左侧对右侧的贡献。此时发现，问题变成了一个先加后求和的问题，即 cdq 分治可以将问题静态化。
先矩形加，随后矩形求和是一个经典问题，扫描线，维护区间加区间求和线段树即可。
具体实现和数据可以在 此处 下载（好像没看到有 OJ 有这个模板（？）可能是都觉得这个没啥意义吧）
点分治
点分治，就是选取树上的一个点 $u$。删掉 $u$ 后树会分成一些连通块，对于每个连通块递归处理。称 $u$ 为分治中心。
如果将 $u$ 选择为任意一个树的重心，那么递归层数是 $O(\log n)$ 的，因为重心最大的那棵子树大小小于等于树大小除以二。
例题 1
题意
给定一棵 $n$ 个点的树，求长度为 $k$ 的路径条数。
$1 \le k \le n \le 10 ^ 5$。
做法
对这棵树点分治。
考虑完全处在一个树内的路径，在点分治后的样子：要么经过分治中心，要么完全处在分治后的某棵子树内。
这是一个很好的性质。对于第二种路径，直接分治下去做即可。
而对于第一种路径，由于其一定经过分治中心 $u$，那么可以将每条路径 $v \to w$ 拆成 $v \to u$ 和 $u \to w$ 两段。计算出分治中心到每个点 $v$ 的距离，设其为 $d _ v$。
之后要求的就是满足 $d _ v + d _ w = k$ 且 $v$ 和 $w$ 不在分治后同一子树内的点对数。
考虑容斥掉后一个条件，即先计算 $v$ 和 $w$ 任选的时候的答案，再对于每一棵分治后的子树减去 $v$ 和 $w$ 都在其中的答案。
将 $d$ 放到其值域上考虑，这样只需要枚举一个量，而另一个量可以直接算出来。由于 $d$ 的值域不会超过其子树大小，因此枚举的复杂度是正确的，最多只是这棵树的节点数。
对于这个分治结构而言，每一层的复杂度是 $O(n)$ 的，总共有 $O(\log n)$ 层，所以复杂度是 $O(n \log n)$ 的。
bonus：分别求出长度为 $1 \sim n$ 的路径条数。
做法是，发现其点分治后的求答案形式是一个卷积，因此使用快速的卷积算法即可快速求出答案。
从这个题中可以看出，点分治可以解决一部分树上路径相关的问题。
例题 2
题意
给你一棵 $n$ 个点带点权的树，第 $i$ 个点的点权为 $v _ i$，另给定 $k, r, y$，满足 $0 \le k, r, v _ i < y$。
定义有向路径 $s \to e$ 的权值：
设从 $s$ 到 $e$ 的路径经过的点的点权分别为 $z _ 0, z _ 1, \cdots, z _ l$，则该条路径的权值为 $z _ 0 k ^ 0 + z _ 1 k + z _ 2 k ^ 2 + \cdots + z _ l k ^ l$ 对 $y$ 取模后的值，记为 $t(s \to e)$。另定义函数 $f(x) = [x = r]$，即当 $x = r$ 时 $f(x) = 1$，否则 $f(x) = 0$。
现在让你求满足以下条件的三元组 $p _ 1, p _ 2, p _ 3$ 的个数：
- 三个点可以相同。
- $f(t(p _ 1 \to p _ 2)) = f(t(p _ 1 \to p _ 3)) = f(t(p _ 2 \to p _ 3))$
$1 \le n \le 10 ^ 5, 2 \le y \le 10 ^ 9$，$y$ 是质数。
题目来源：CF434E
做法
考虑转化 $f(t(p _ 1 \to p _ 2)) = f(t(p _ 1 \to p _ 3)) = f(t(p _ 2 \to p _ 3))$。由于 $f$ 函数值域是零和一，可以将它改写成以下形式：
$f(t(p _ 1 \to p _ 2))f(t(p _ 1 \to p _ 3))f(t(p _ 2 \to p _ 3)) + (1-f(t(p _ 1 \to p _ 2)))(1-f(t(p _ 1 \to p _ 3)))(1-f(t(p _ 2 \to p _ 3)))$
设 $a _ u$ 为 $\sum \limits _ {v = 1} ^ n f(t(v \to u))$，$b _ u$ 为 $\sum \limits _ {v = 1} ^ n f(t(u \to v))$。将上式拆开后，可以发现 幸亏三次方项被消去，就是说可以将答案表达为仅关于 $a$ 和 $b$ 的式子。具体的式子较为繁琐，不在此详细展开，留作读者作业。
现在只考虑求出 $a$，而 $b$ 的求法是类似的，不在此详细说明。
对这棵树点分治。在 $u$ 和 $v$ 仍处在一个分治子树内，且下一层就不在的时候计算 $v \to u$ 的贡献。
把路径权值从分治中心处拆成两部分，和上一题类似的，放到值域上考虑，然后类似的容斥一下；不过由于值域很大所以需要使用哈希表来记录。
动态点分治
即维护点分治的结构。
所谓点分树，就是将每一层的分治中心向其上一层所在的分治子树的分治中心连边所形成的有根树。这样可以快速统计以某个点出发的所有路径的信息，具体的，从这个点不断在点分治树上跳祖先即可。
例题 1
题意
小 M 在玩一个游戏，这个游戏的地图是一个 $n$ 个点的树。
每个结点有两种可能的状态：「已知的」或「未知的」。游戏开始时，只有 $1$ 号结点是已知的。
在游戏的过程中，小 M 可以尝试探索更多的结点。具体来说，小 M 每次操作时需要选择一个已知的结点 $x$，和一个不同于 $x$ 的任意结点 $y$（结点 $y$ 可以是未知的）。然后游戏的自动寻路系统会给出 $x$ 到 $y$ 的最短路径上的第二个结点 $z$，也就是从 $x$ 走到 $y$ 的最短路径上与 $x$ 相邻的结点。此时，如果结点 $z$ 是未知的，小 M 会将它标记为已知的。
这个游戏的目标是：利用至多 $T$ 次探索操作，让所有结点的状态都成为已知的。
此题为交互题，你需要实现函数 void play(int n, int T, int dataType); 来使得所有结点均已知，其中 dataType 会告诉你子任务类型。你可以在此函数中调用 int explore(int x, int y); 函数来完成一次探索，此函数会返回 $z$。
- 子任务 $1$：$n = 3 \times 10 ^ 5, T = 3 \times 10 ^ 5 + 20$，保证树是一条链。
- 子任务 $2$：$n = 3 \times 10 ^ 5, T = 5 \times 10 ^ 6$，不保证树的形态。
题目来源：WC2018 即时战略。
做法
首先考虑一个暴力做法：可以随机一个未知的结点的编号，然后不断从某个已知结点走向它，直到到达这个未知结点。不断重复这个过程，就能探索完全部结点。
不过这样询问次数是平方的，无法通过任何一个子任务。
考虑链的做法：当前已知的结点也一定形成一条链，而且后续新探索到的结点会被加在链的两边。于是可以维护当前链的两个端点，每次随机一个点 $y$ 之后尝试从一个端点出发去新探索一个点。如果不能探索，就从另一个端点向 $y$ 前进；否则就直接向 $y$ 前进。由于每次随机期望减少 $\frac{1}{4}$ 的未知结点，但每次随机只有 $\frac{1}{2}$ 的概率浪费一次探索机会，因此总探索次数期望是 $n + \log _ 2 n$ 左右的。
考虑树的做法，依旧可以优化暴力。
考虑如何用较少的探索次数找到已知结点到某未知结点 $y$ 路径上的第一个未知结点。
经过一些人类智慧，发现这个可以利用点分治的结构来将其优化至 $O(\log n)$。具体的，将所有已知结点建出一棵点分树。随后从点分树的根 $u$ 开始探索，求出它到 $y$ 路径的第一个结点 $z$。如果是未知的，那么就完成了这一任务；如果是已知的，那么第一个未知结点的之前那个点就一定在点分树上 $u$ 的子树中包含 $z$ 的那一棵子树，如此沿着点分树探索即可。
探索一个点要花费 $O(\log n)$ 的时间，那么探索完所有点就只用 $O(n \log n)$ 的时间。
但是，在动态加点时，如何维护这个点分树的结构而不让它树高退化呢？
其实可以像替罪羊树那样，如果某棵子树的大小已经大于当前树的大小乘以系数 $\alpha$，那么就直接重构这棵子树。$\alpha$ 一般取到 $0.7$ 左右来平衡复杂度。
边分治
边分治其实和点分治很类似的！在选边的时候挑一个两侧子树点数差最小的边，随后分治成两部分做。
但是这样在菊花图下时间复杂度会爆炸。可以将这棵树『三度化』，之后再如上方式选边即可确保复杂度不爆炸，递归层数是 $O(\log n)$ 的。
三度化是指，通过添加一些新点和新边，使得每个点的度数都小于等于三。一般是对于一个点和其孩子间添加。添加的方式有很多种，比如可以类似线段树的方式，也可以搞一条链，链上每个点有一个孩子。
复杂度证明：考虑找到一棵 $n$ 个点的树的重心，如果选择它和它最大的子树间的那条边，那么分治下去的两部分点数均在 $[\frac{1}{3}n, \frac{2}{3}n]$ 之间，所以只会递归 $O(\log n)$ 层。
一般而言，点分治能做的题边分治都能做；不过边分治代码量大，常数也较大，所以一般选用点分治。但是在一些题目中需要分治出的集合数量比较少，这时就只能使用边分治了。
图分治
图分治，就是有一类特殊图，它们有一些很优秀的适合分治的性质。
没有广义串并联图，因为我不会。
图分治这个名字我乱起的
例题 1
题意
有一个 $n$ 个点的无向环，边有非负整数边权。在环内（可以将环看成一个正多边形的样子，顶点顺时针标号）有 $m$ 条无向边，这些边不会与环上原有的边重合，也不会有自环。这些边没有在端点外的交叉，也不会重合。
对于任意两点 $u, v$，定义 $dis(u, v)$ 为从 $u$ 到 $v$ 的最短路长度。
求 $\sum \limits _ {i = 1} ^ {n - 1} \sum \limits _ {j = i + 1} ^ n dis(i, j)$。
$n, m \le 2\times 10 ^ 5$，边权非负。
题目来源：阚神 圆 LOJ6898
做法
先补全为多边形的三角剖分，这个随便构造一下，注意些细节就可以了。
随后我们直接分治。选择一条非环边 $(x, y)$，使之尽量平分整个多边形。可以发现，$x, y$ 成为了左侧和右侧的必经之路。
分别从 $x$ 和 $y$ 出发跑一次最短路。那么对于一个左侧点 $u$ 和一个右侧点 $v$，$dis(u, v) = \min(dis(u, x) + dis(x, v), dis(u, y) + dis(y, v))$。如果钦定这个 $\min$ 取到 $dis(u, x) + dis(x, v)$，我们可以得到 $dis(u, x) + dis(x, v) < dis(u, y) + dis(y, v)$，即 $dis(u, x) - dis(u, y) < dis(y, v) - dis(x, v)$。这个可以直接排序，然后双指针求出其和的。对于另一种情况则是类似而相反的，不赘述。
因此我们可以求出左侧和右侧间的最短路和。继续分治下去，让 $x, y$ 既在左侧也在右侧，其边权为 $dis(x, y)$。
复杂度证明：考虑包含正 $n$ 边形的中心的那个三角形。它的边所对应的短弧中最长的，在 $[\frac{1}{3} n, \frac{1}{2} n]$ 之间，因此递归层数是 $O(\log n)$ 的。
被广义串并联图爆了，伤心
例题 2
题意
给定一张 $n \times m$ 的网格图，边有非负边权。$q$ 次给定两个点，查询其之间的最短路长度。
$n\times m \le 2\times 10 ^ 4, q \le 10 ^ 5$
题目来源：ZJOI2016 旅行者
做法
首先将询问离线下来，设 $A = n\times m$。考虑沿较宽的一边的中间分开来分治。中间的点数一定小于 $\min(n, m)$，也就是小于 $\sqrt A$。从这些点上分别向当前分治的网格图中所有点跑一次最短路。考虑对于每个询问：如果该询问最短路径经过中间这些点，那么可以通过枚举经过哪个点并求得答案；如果不经过中间的点，那么这次询问的两个点一定都在此次分开后的某一侧，分治下去处理。
复杂度是，对于处理最短路：$T(A) = 2T(\frac A 2) + O(A\sqrt A\log A)$，根据主定理得到复杂度是 $O(A\sqrt A \log A)$。对于某次询问，最大是 $O(\sqrt A + \sqrt{\frac A 2} + \sqrt{\frac A 4} + \cdots) = O(\sqrt A(\sum _ {k = 1} ^ \infty (\frac 1 {\sqrt 2})^k)) = O(\sqrt A)$。所以总复杂度是 $O(A\sqrt A \log A + q\sqrt A)$。
例题 3
题意
给定一个 $n$ 层的完全二叉树（$2 ^ n - 1$ 个点），单向边，都是孩子向其父结点连。另给定 $m$ 条从祖先连到孩子的单向边。求此图上两两最短路的和，如果某两个点不连通则认为其最短路为 $0$。边权非负，$n \le 18, m \le 2 ^ n$。
题目来源：NOI2023 贸易
做法
二叉树本身就是一个非常优秀的分治结构。发现对于两个点而言，它们的路径一定会经过其在树上的 LCA。于是考虑在 LCA 处计算其贡献。
具体的，从每个点出发，向其子树内跑一遍最短路（反图可以直接做而不必使用最短路），然后分别计算能到达左子树多少个点，右子树多少个点，和分别的最短路和。然后随便乘一乘加一加就能得到答案了。
问题在于最短路怎么跑。发现一个点到其子树的路径是有可能离开子树的！不过它只会经过 LCA 到根的路径上的点。但是仍旧不能暴力跑最短路。假如 $m$ 条边都在根上，那么每次都要遍历一遍，然后就 TLE 了。所以可以考虑优化：遍历子树内的点所连的边，只将这些边加入要跑的最短路即可。由于每个点只会被遍历 $O(n)$ 次，因此每条边被加入的次数也是 $O(n)$ 的。总复杂度是 $O(n ^ 2 2 ^ n)$。
其它复杂分治
一些难以分类的较为困难的分治。 分治杂题宣讲
rprmq1
题意
有一个 $n \times n$ 的矩阵 $a$，初始全是 $0$，有 $m$ 次修改操作和 $q$ 次查询操作，先进行所有修改操作，然后进行所有查询操作。
一次修改操作会给出 $l_1,l_2,r_1,r_2,x$，代表把所有满足 $l_1 \le i \le r_1$ 且 $l_2 \le j \le r_2$ 的 $a_{i,j}$ 元素加上一个值 $x$。
一次查询操作会给出 $l_1,l_2,r_1,r_2$，代表查询所有满足 $l_1 \le i \le r_1$ 且 $l_2 \le j \le r_2$ 的 $a_{i,j}$ 元素的最大值。
$1 \le n, m \le 5 \times 10 ^ 4$，$1 \le q \le 5 \times 10 ^ 5$。
题目来源：Ynoi rprmq1
做法
首先可以对加法操作做差分。
对一维猫树分治，另一维使用区间加区间历史最大值（也许可持久化）线段树维护。
关于区间加区间历史最大值的维护：考虑 $(\max, +)$ 的矩阵乘法，应该是容易维护的。
关于猫树分治：简单介绍一下猫树：在线段树的结构基础上，对于线段树每个结点，分别维护出从中点到左右两侧的每个信息。这样对于任意一个区间，只需要一次信息合并即可获得其答案。
猫树分治就是像猫树一样分治。对于询问，将其放在猫树上的某个区间中处理。
在此题中，只需要得到最左侧的线段树，就可以将其移到中间，重置历史最大值，然后分别向左右扩展计算。
复杂度 $O(m \log ^ 2 n + q \log n + n \log n)$。
另个最小化题
题意
给定一个序列 $a _ {1, 2, \cdots, n}$，要把它分成 $k$ 个子段。每个子段的费用是其中相同元素的对数。求所有子段的费用之和的最小值。
$1 \le n \le 10 ^ 5$，$1 \le k \le \min(n, 20)$。
题目来源：CF868F
做法
考虑一个朴素的 dp：$f _ {i, j}$ 表示前缀 $[1, i]$ 被划分为了 $j$ 个子段时其费用和最小值。
随后我们发现它有决策单调性，即 $f _ {i, j}$ 的转移点一定不会比 $f _ {i - 1, j}$ 的转移点靠前。证明略去，大家可以感性理解。
交换 dp 的两维，然后，直接分治！
分治求出 $f _ {j, [l, r]}$ 的值，已知决策点在 $[L, R]$ 中。考虑找到 $m = \lfloor \frac{l + r}{2} \rfloor, f _ {j, m}$ 的决策点（计算时只需要对 $[L, R]$ 内的求出其转移！），就可以知道 $[l, m - 1]$ 和 $[m + 1, r]$ 的决策点位置，接着分治下去。
剩下一个问题是，如何快速求出转移。其实这个直接类似莫队的维护一个区间暴力扫过去即可，随便分析一下复杂度就发现它和分治是一个复杂度了。
总复杂度 $O(kn \log n)$。
这似乎是决策单调性的常见用法……不过没听说过就感觉很高妙阿。
