自动搬运

查看原文

来自洛谷，原作者为

	Yonder Morose Dreamer

搬运于2025-08-24 23:08:30，当前版本为作者最后更新于2025-01-13 15:59:19，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

简单题。

考虑对 $l$ 从大到小扫描线，维护一个数组 $a$，每次把 $a_{bot_i}$ 修改为 $i$。

注意到从 $l$ 开始一直到 $n$，$\text{mex}$ 是单调递增的，那么我们只需要求出第一次 $\text{mex}\ge x$ 和第一次 $\text{mex}>y$，显然分别为 $\displaystyle\max_{0\le i<x}a_i,\displaystyle\max_{0\le i\le y}a_i$。

用线段树维护 $a$ 数组即可。