[DS记录]P5611 [Ynoi2013]D2T2

command_block · 2020-10-31 21:58:05 · 个人记录

题意 : 给一个长为 n 的序列，有 m 次查询操作。

每次给出 l,r,L,R ,询问将序列中值在 [L,R] 内的位置保留不变，其他位置变成 0 时，序列中 [l,r] 内的最大子段和。

允许离线，n,m\leq 10^5 ,时限\texttt{1s} ，空限\texttt{64M}。

先不考虑 [L,R] 的限制，求在 [l,r] 内的最大子段和是非常简单的。

这启发我们用莫队处理 [L,R] ，用线段树维护最大子段和，复杂度为 O(n\sqrt{n}\log n) ，无法通过。

若不考虑 l,r 的限制，求全局值在 [L,R] 内的最大子段和。

如果能在 O(m^2) 的复杂度内求出一个长为 m 的序列的所有定值域最大子段和信息(即最大前缀和，最大后缀和，全局最大子段和)，那么分块就能做到 O(n\sqrt{n}) 的复杂度。

离散化之后，长为 m 的序列只有 O(m^2) 个可能的值域区间，称之为关键区间。

若要查询 [a,b] 的答案，就需要找到最大的被 [a,b] 包含的关键区间 [a',b']。

考虑分治，枚举一个值域区间 [a,b]。

查询左右儿子 [a,b] 内的最大子段和信息，容易合并出整个区间的答案。方法如上。

找到最大的被 [a,b] 包含的关键区间 [a',b'] 这一过程不能使用二分，这样会使得复杂度多 \log。

考虑按照 b 递增的顺序枚举 b ，这样 b' 也就只会递增，复杂度就不带 \log 了。

这样的复杂度是 T(n)=2T(n/2)+O(n^2)=O(n^2)。

查询时，散块容易在 O(\sqrt{n}) 内完成。

对于整块，计算 [a',b'] 时同样不能使用二分，可以把询问 (按照 L,R 分别) 排序之后批量(离散化)处理。也可以把前驱打表。

然而，每个块的空间消耗是 O(\sqrt{n}^2)=O(n) 的 ，总空间复杂度就是 O(n\sqrt{n}) ，无法承受。

离线逐块处理即可。