P4137 Rmq Problem / mex 题解

link T2 desu. T1 太简单了没写

一眼莫队是真的。

不过这里有个小细节：拿到这道题的时候考虑的莫队是只增不减的回滚莫队，但其实这样复杂度会假。

为什么？考虑只增不减的 $mex$ 怎么写

while(l<nowl){
    ++tong[a[--nowl]];
    while(tong[mex]) ++mex;
}

你可知道这是回滚莫队。

假如构造一个除了 $1$ 和 $114514$ 其他都出现的情况，$l$ 的块内有一个 $1$，然后反复碾压块内。这样就会导致这里面的所有询问，$mex$ 都要跑一遍 $1\rightarrow 114514$。

反正就是他会反复跑 while 循环，然后 #12 tle。

---

正确做法是考虑只减不增。

每个块只会跑一遍向上增大 $mex$，这样是 $O(n)$。然后考虑删掉一个值后是否会影响 $mex$ 即可。

submission