自动搬运

查看原文

来自洛谷，原作者为

	mrsrz 故障机器人

搬运于2025-08-24 22:28:26，当前版本为作者最后更新于2021-01-27 15:07:16，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

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

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

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

$m$ 组询问，每次给出 $l,r,x,y$，要求对一个初始为空的序列执行编号在 $x$ 到 $y$ 之间的操作，然后查询区间 $[l,r]$ 的最大值。

考虑对区间加进行差分，即将 $[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)$，实现时需要注意常数因子。