2026年5月专项训练巩固总结

序列分治

先给一个例题，给你一个序列，要求所有区间的最小值的和。

我们考虑如何求解所有包含在 $[l, r]$ 区间里的子区间 $[i, j]$ 的最小值之和，我们记 $mid = \frac{l + r}{2}$，可以把这些区间分 3 类去计算贡献：

• 把所有包含在 $[l, mid]$ 区间里的子区间的最小值的和算出来。
• 把所有包含在 $[mid + 1, r]$ 区间里的子区间的最小值的和算出来。
• 计算 $i \in [l, mid]$，$j \in [mid + 1, r]$ 的子区间 $[i, j]$ 的最小值的和。

我们记 calc(l, r) 是算上面提到的东西的，那么前两个步骤就是 calc(l, mid) 和 calc(mid + 1, r)。

需要思考的是跨中点的 $[i, j]$ 的贡献怎么算。

我们考虑枚举左端点 $i$，再枚举右端点 $j$，则最小值就是 $[i, mid]$ 和 $[mid + 1, r]$ 的最小值的最小值。

现在这种合并需要 $O(n^2)$ 的时间，甚至不如直接暴力枚举区间。

考虑加速，我们能否只枚举 $i$，然后快速算出所有 $j$ 的最小值的和？

这是可以做到的，记 $[i, mid]$ 的最小值是 $mn$，则要么对所有 $j \in [mid + 1, r]$，都有 $[mid + 1, j]$ 的最小值大于 $mn$，要么存在某个 $k$，使得 $j \in [mid + 1, k]$ 时最小值都大于 $mn$，对于 $j \in [k + 1, r]$ 最小值都不超过 $mn$。只要知道这个位置在哪儿，就可以分这两段算。只要多维护一个前缀和就行了。

上述提到的，先递归解决左半边和右半边各自的答案，再想办法快速计算跨中点的答案的思路，就是序列分治。

序列分治的效率主要取决于合并有多快。为了快速合并，我们一般得维护从中点往两边的某些信息，以及一些前后缀相关的信息，可以想想区间最大子段和是怎么做的。

序列分治的应用范围：

• 统计所有点对/所有子区间的信息
• 从中间往两边扩展时，维护的属性有单调性，且左右维护的信息可合并，则可以高效维护。

破环为链

举几个具体的例子：

P3091

本题需要判断两个极角区间是否有交集。

我们面临的第一个困难是，求出来的极角区间（用度表示）可能有 $[-30, 40], [20, 100], [300, 400]$ 这种的。我们的解决方案是将所有区间的左端点放到同一圈上，也就是变成 $[330, 400], [20, 100], [300, 400]$。

第二个困难是，$[300, 400]$和 $[20, 100]$ 其实是有交的，但是 $[300, 400]$ 的右端点到了下一圈里，它其实是 $[300, 360]\bigcup [0,40]$。我们的解决方案是，把每个区间在下一圈的表示也加进来，比如加入 $[380, 460]$，这样就和 $[300, 400]$ 有交了。

第三个困难，或者说顾虑，是在加入下一圈的表示后，会不会出现同一个区间本圈和下一圈自交的情况？其实是不会的，因为根据题目限制，我们的极角区间长度最多也就是 $180$，而下一圈则是需要左右端点同时加 $360$，所以必然不会相交。

至此，我们只需要所有区间按左端点排序，然后枚举区间，利用二分看后边有多少其他区间的左端点落在了自己的区间里面即可了。

KMP自动机+DP

动态DP