第六分块时间轴分块题解

金珂拉 · 2022-10-21 20:33:20 · 题解

因为大家写的都是序列分块基数排序套闵可夫斯基和，于是我来写一个既不用序列分块也不用闵可夫的对时间轴分块加普通凸包的版本。

时间轴分块是好文明。

弱化版

首先，先考虑一个全局修，全局查最大前缀和、最小前缀和，以及一个全局最大子段和的结构怎么做？

先将整个序列做一个前缀和。考虑第 i 个位置，全局加了 d 之后，这个位置上的值变为 S_i={S_i}_0+i\times d

这是一个关于 d 的一次函数。于是我们把它当作一条直线，于是我们只需要维护这个 S_i 即可。

我们发现这两个东西可以看成多个半平面的交，且半平面是递增的。于是我们考虑每个点维护由这多个直线分别构成的上凸壳和下凸壳。

下凸壳同理。

然后考虑全局最大子段和。

我们对每个点维护 R,L 两个数组，表示以这个点为左端点/右端点的所有序列中至少有一个非负需要的最小的加值。

这个可以在 i-S 图里迅速线性维护。具体的，我们考虑 L，则有

于是我们就可以维护一个斜率优化了。具体的，我们从右往左扫描过去，每次往当前的凸包里加一个数的同时在当前凸包里做一下。

容易发现答案是单调的，因此我们可以直接在凸包上暴力做，时间复杂度 O(N)

然后我们考虑如何根据这个计算最大子段和。容易想到的是，最大子段一定是极大子段：若有一个子段 B 与子段 A 相交、相接触或相包含，则合并 A 与 B 后得到的子段和一定大于 B 的子段和。

于是我们就可以考虑到，极大子段中一定不存在负数前缀和与负数后缀和。即，一个极大子段内的所有数，都满足以其为左端点/右端点的子段中至少有一个比他大。

然后我们就想到维护按照左右边界维护极大子段，然后随着 d 的增加按顺序合并极大子段，并且最后把所有极大子段转一次函数放到凸包里就行。

强化版

我们发现这次是区间修。

于是我们每 \sqrt N 个询问分一组。

这样子，序列就被这些询问分成了 O(\sqrt N) 个部分。考虑每一部分，发现都可以看作一个全局修，全局查。

于是我们就直接线性地求出每个区间的最大前缀和，最小前缀和，最大子段和的凸包，然后对每个询问通过全局的排序（这里可以直接每组排序一次或者整体排序，因此不需要基数排序了）处理掉的情况，最终就直接普通的递推合并即可。

最终复杂度 O(\dfrac M{\sqrt N}N+M\sqrt N) =O(M\sqrt N)

代码咕了。