自动搬运

查看原文

来自洛谷，原作者为

	mrsrz 故障机器人

搬运于2025-08-24 22:12:32，当前版本为作者最后更新于2020-02-20 10:47:42，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

第七分块太难了就先来写一下这个。

结果交了 59 发才过……

有一个非常简单的做法，将值域离散化之后对值域进行莫队，用线段树维护最大子段和。时间复杂度为 $O(n\sqrt m\log n)$。

考虑更优的做法。如果我们有一种时间复杂度 $O(n^2)$ 的做法求出一个长度为 $n$ 的序列的所有不同值域限制下的全局最大子段和，那我们就可以通过分块将这个复杂度降为 $O(n\sqrt n)$。

关于最大子段和的问题，分治是一个常见的思路。由于长度为 $n$ 的序列，只有 $O(n^2)$ 个本质不同的值域限制，所以我们希望每层都能 $O(n^2)$ 合并信息。这样分治的复杂度为 $T(n)=2T(\frac n 2)+O(n^2)$。根据主定理即可得到 $T(n)=O(n^2)$。

我们考虑已知两个子区间的本质不同的值以及限制，如何合并为这一层的答案。对于合并上来的 $[L,R]$，我们需要在左、右分别找到区间 $[L_1,R_1]$ 和 $[L_2,R_2]$，其中 $[L_1,R_1]$ 和 $[L_2,R_2]$ 都是被 $[L,R]$ 包含的最大区间。那么这两个区间的最大子段和信息进行合并，即可得到 $[L,R]$ 的最大子段和信息。

我们考虑预处理对每个 $L$，左、右区间第一个大于等于 $L$ 的值。同样，对于 $R$，预处理左、右区间第一个小于等于 $R$ 的值。由于我们是要选最大的两个区间合并，那么两个端点和 $L,R$ 最接近的一定是最大的。这样就可以直接 $O(n^2)$ 枚举 $L,R$，然后 $O(1)$ 找到两个需要合并的区间，进行合并。

分治的时空复杂度均为 $O(n^2)$，考虑对序列分块，每个块的大小为 $O(\sqrt n)$，则对每个块进行分治的时间复杂度为 $O(n)$。分治花费的时间复杂度为 $O(n\sqrt n)$。

对于一个询问，拆成整块的和边角的。对于边界的显然可以 $O(\sqrt n)$ 解决。对于整块的，我们已经知道所有本质不同的值域限制的答案，那么对于值域限制为 $[L,R]$ 的询问，我们要找到被它包含的最大的区间的信息。那么和上面的处理方式相同，对每个 $L$ 和 $R$ 分别找到最靠近的端点即可。这里为了保证复杂度，必须用双指针处理，否则时间复杂度将退化为 $O(m\sqrt n\log n)$。

由于直接存储所有块的信息需要 $O(n\sqrt n)$ 的空间，无法接受。所以我们对询问离线，在一个块的信息处理完后，直接把这个块对所有询问的贡献都更新掉。这样空间复杂度为 $O(n)$。

时间复杂度为 $O((n+m)\sqrt n)$。

注意实现时的常数。