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

· · 题解

思路

首先求出以 1 为 l 的所有区间的 \mathrm{mex}，这个可以用 set 维护一下没有出现过的最小值，接下来把左端点右移，对全局的影响即在后一个相同数字之前的右端点的区间 \mathrm{mex} 与其取最小值，线段树维护区间最小值即可。最后把询问离线下来，发现左端点相同每次移动右端点后面的答案一定是不减的（证明很简单，没有出现的数集不会新加进数），直接在线段树上二分即可，时间复杂度 O(q\log n)。