题解 P5611 【[Ynoi2013]D2T2】

mrsrz · 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)。

注意实现时的常数。