Mex を求めるアルゴリズム
まずは問題を保留して，vector \(a\) が与えられたとき，\(mex(a)\) を求める手順を考える．
小さい自然数から実験してみれば，\(i \in \mathbb{N}\) に対して， \(mex(a) = i\) となるのは，任意の\(j \in i\) に対して \(j \in a\) かつ \(i \not \in a\) であることと同値であると分かる．
よって，次の手順で \(mex(a)\) が求まる． 実装するなら，N := size(a) とおいて， for i in N
   \(i \not\in a\) なら \(mex(a) = i\) が確定して break．
   \(i \in a\) なら \(mex(a) > i\) が確定して次のループへ．
このループが終わっても確定してなければ，\(mex(a) = N\) と確定する．
今回の問題
上を踏まえて，今回の問題に当てはめてみる． \(N\) における長さ \(M\) の区間 \(I\) を動かす． ans \(\leq N\) は確定している． ans の候補 for i in N を調べていくことになりそうなので， 小さい \(i\) から \(ans = i\) になる条件を実験して探る．
- ans = 0 となるのは，ある \(I\) が存在して \(0 \not \in a_{I}\) と同値．
- ans = 1 となるのは，ans \(\neq 0\) かつ，ある \(I\) が存在して \(1 \not \in a_{I}\) と同値．
- ans = 2 となるのは，ans \(\neq 0\) かつ ans \(\neq 1\) かつ， ある \(I\) が存在して \(2 \not \in a_{I}\) と同値．
これを繰り返すと，次のアルゴリズムを得る．
for i in N
   ある \(I_{0}\) が存在して \(i \not\in a_{I_{0}}\) ならば， \(ans = min_{I} mex(a_{I}) = i\) が確定して break．
   そうでなければ， \(ans > i\) が確定して次のループへ．
このループが終わっても確定してなければ，\(ans = N\) と確定する．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
