自动搬运

查看原文

来自洛谷，原作者为

	zhenjianuo2025 Still we'd fight until our last

搬运于2025-08-24 23:05:18，当前版本为作者最后更新于2024-09-26 09:13:08，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

将 $(y,x)$ 的点视作 $[x,y]$ 的区间，现在问题转化为维护区间集合 $S$，支持：

• 动态修改 $S$ 中的某个元素；
• 查询 $S$ 内被给定区间 $[l,r]$ 包含的区间中最短的区间。

对于一次询问操作 $[l,r]$：

• 找到 $x_0\ge l$ 的最小的 $y_0$；
• 求出 $y_0\le y\le r$ 的最小的 $y-x$ 的值。

可以证明这是正确的：

• 一方面，对于任何合法的区间 $[x,y]$，因为 $y\ge y_0$，必定会被计入答案之中。
• 另一方面，考虑一个 $y_0\le y\le r$ 且 $x<l$ 的不合法区间 $[x,y]$，由于 $y-x>y_0-l\ge y_0-x_0$，所以必定不会对答案造成任何影响。

上面两项都可以使用线段树简单维护。用 std::mutiset 辅助存储每个左端点对应的右端点集，以及每个右端点对应的左端点集。修改时单点修改两棵线段树上的对应位置。时间复杂度 $\Theta\left((n+q)\log n\right)$，可以通过。

其他任何想法欢迎与我私信交流。