题解 P7290 【「EZEC-5」暴力出奇迹】

mrsrz · 2021-01-27 15:07:16 · 题解

这篇题解仅讲述问题的转化。

先将题意转述为更容易理解的形式。

有 n 个操作，第 i 个操作为 [l_i,r_i]，表示对 [l_i,r_i] 区间加一。

考虑对区间加进行差分，即将 [l,r] 的区间加变成 l 处加一，r+1 处减一，然后区间查询，相当于查询右端点在 [x,y] 内的前缀的最大前缀和。不难发现，1\sim x-1 处的值一定会被统计到答案中，因此可以把询问分成查询 [1,x-1] 的和，以及 [x,y] 的区间最大前缀和。前者可以使用二维数点在 O(n\log n+m\log n) 内解决，重点在于求出后者。

对每个 i，从 [l_i,r_i] 中可以得到两个三元组 (l_i,i,1)，(r_i,i,-1)。

我们将所有三元组以第一个元素为关键字从小到大排序，得到一个长度为 2n 的三元组序列。我们称位置 i 的第三个元素为位置 i 的值（为保证结果正确，在第一个元素相同时，值为 1 的在前）。然后一次查询的 [x,y] 对应这个序列上的一个区间。

于是现在的查询操作实际上是：仅保留第二个元素在 [l,r] 内的位置的值，其他位置的值为 0 时，查询 [x,y] 对应的区间的区间最大前缀和。

这个问题有一个强化版的问题，查询的是最大子段和信息，而维护该信息的同时需要维护本题所需的最大前缀和信息。因此直接使用该题的做法即可解决本题。具体可以见我的题解。

该做法的时间复杂度为 O((n+m)\sqrt n)，空间复杂度为 O(n+m)，实现时需要注意常数因子。