P11570 「chaynOI R1 T3」镍铬合金机器人

_Yonder_ · 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 数组即可。