エゴサしたらこの記事がわりと読まれているっぽかったものの、やや実装が重い気がしたので*1別の解法を書きます。
tl; dr
セグ木。
定義
有限集合 \(S\subseteq \N\) における mex というのは、\(S\) に含まれない最小の自然数 \(\min_{i\in \N\setminus S} i \) です。
やりたいこと
- 追加：\(S\gets S\cup\{i\}\) で更新
- 削除：\(S\gets S\setminus\{i\}\) で更新
- mex：\(\min_{i\in \N\setminus S} i\) を出力
これを (amortized) \(O(\log(|S|))\) 時間とかで。
アイディア
クエリ数が \(n\) のときのことを考えます。このとき、mex が \(n\) を超えることはないことに注意します。 \(S = \{0, 1, \dots, n-1\}\) のとき最大値 \(n\) になります。
そこで、bool の配列 \(a = (a_0, a_1, \dots, a_{n-1})\) を \(a_i = (i\in S)\) が保たれるように管理します。
求めたい mex は、\(\wedge_{i\in[0, x)} a_i\) が true になる最大の \(x\) です（このとき \(a_x\) が false となり、定義から \(x\notin S\) となるので）。
よって、\(a\) をセグ木で管理し、この \(x\) を二分探索（ACL で言うところの max_right）で求めればよいです。
\(n\) 以上の値を \(S\) に入れると（クエリ数 \(n\) の下で）mex は \(n\) 未満になることに注意すると、\(n\) 以上の値の更新クエリは無視してよいです。
クエリ数の仮定の除去
クエリ先読みができないときとか、そういう仮定が気に食わないとかで、\(n\) の決め打ちをしたくないことはあります。 そこで、いつものテクを使います。
まず、\(n = 1\) と思って処理します。 \(|S| = n\) になったら \(n\gets 2\cdot n\) で更新し、今までの \(|S|\) に基づいて \(a\) を再構築します。無視されていたもののうち \([n, 2n)\) の値が新しく考慮されることになります。
再構築は \(O(n)\) 時間でできるので、（償却）計算量を悪化させません。
あるいは、mex が \(|S|\) になる限り倍々に増やすとかでもよいです。
あ
冷静になると、（\(n\) を倍々にできるので）\(\{0, 1, \dots, n\}\setminus S\) を std::set で管理して upper_bound とかすればよくないですか？
セグ木を使う場合でも、\( (i\in S\cap\{0, 1, \dots, n-1\}, i)\) の pair を持って全体の \(\min\) を計算する手もあります。
発展編
ひとつめ
もう少しリッチなクエリを処理したくなるときもあります。 \(S\) を集合ではなく配列とします。
- 初期化：\(S \gets ()\)
- 末尾への追加：\(S \gets S \concat\, (x)\)
- \(\concat\) は
[1,2,3] ++ [4,5] == [1,2,3,4,5]のイメージ。 - \( (x)\) は 1 要素の配列のこと。
- \(\concat\) は
- 区間 mex：\(\mex\,\{ S_i \mid i\in[l, r) \}\)
- さっきのは \(l=0\) と見なせる。
さっきと同様にとりあえずクエリ数を \(n\) とします。また、一旦は \(r = |S|\) として考えます。 \(a = (a_0, a_1, \dots, a_{n-1})\) を管理し、\(S\) における \(i\) の最後の出現位置を \(a_i\) とします。出現していないときは \(-\infty\) とします*2。
mex クエリの答えは、\(\wedge_{i\in[0, x)} (a_i \ge l)\) となる最大の \(x\) で、\( (\min_{[0, x)} a_i) \ge l\) となる最大の \(x\) を求めればよいです。セグ木でにぶたんです。
\(n\) の仮定の除去はさっきと同様にします。 \(r\) に関してはちょっと大変です。セグ木に対して「\(|S| = r\) だったときの値は？」という質問をする必要があるので、永続セグ木を使えばよいです。
書きながら思い出したのですが、検索したら見つかりました。
プチ問題
— 寝る (@noshi91) 2020年9月17日
データ構造を設計してください
・construct(A)
長さ N の数列 A からデータ構造を構築
O(N log(N))
・mex(l, r)
mex{A_i | l ≤ i < r} を出力
O(log(N))
例題：
\[ g_i = \begin{cases} 0, & \text{if }i = 0; \\ \mex_{j\in[1, c_i]} g_{i-j}, & \text{otherwise}. \end{cases} \]
\(g_i = x\) を \(g \gets g \concat\, (x)\) だと見なせて、\(l = i - c_i\) に対応します。
最終的な答えは、以下により定まります（\(\oplus\) は xor）。
\[ \bigoplus_{i\in[0, n)} g_i\cdot (a_i \bmod 2). \]
ふたつめ
次に、更新クエリ \(S_i \gets x\) を考えます。これはわかりません。
\(S_i\gets x\) というのは「過去に遡り、\(|S| = i\) のときに \(S\gets S\concat\,(S_i)\) ではなく \(S\gets S\concat\, (x)\) をしたことにする」というのに対応します。
この形式の「過去に遡り、これこれの操作をしたことにする」というクエリを処理するデータ構造は retroactive data structure と呼ばれています*3。
なので、セグ木を retroactive にすればよいのですが、これってできるんですかね。
なんか このポスター の General Approach のところを見ると、non-retroactive DS を retroactive にするような話があるような気がするのですが、一般的なテクはなかったような気がする (https://erikdemaine.org/papers/Retroactive_TALG/paper.pdf :: Theorem 2) ので、わかりません。何らかの文脈があるのかも。
ねむいので今日はここまでです。あとでまた読みます。
めも
他のアプローチとして、更新できる WM でなんとかなったりしない？ んーむずかしいかも。
更新できる方の Mo は使えそう。ちなみにまだ理解してません。
おわり
ねこ。
