P11764 题解

· · 题解

所有操作独立，所以只需要考虑一个数 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 则无解。