自动搬运

查看原文

来自洛谷，原作者为

	lmh .

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

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

以下是正文

所有操作独立，所以只需要考虑一个数 $a_x$。

显然合法的 $k$ 只有两种取值：要么所有区间都合法，此时 $a_x\in [y-p,y+p]$；要么不包含 $x$ 的区间合法，此时 $a_x\notin [y-p,y+p]$。

首先考虑第一类限制，它可以把 $a_x$ 的范围缩小到一个区间 $[L,R]$；然后按照左端点从小到大考虑第二类限制 $[l,r]$，如果 $L<l$ 则 $L$ 合法，否则 $L\leftarrow \max\{L,r+1\}$，如果 $L>R$ 则无解。