コンテスト中に見に来た人へ：コンテスト後、この記事にある方法以外についても復習しておくのをおすすめします。

自然数（\(0\) を含むよ）の集合において、mex というのは、minimum excludant (minimum excluded) の略で、それに含まれない最小の自然数のことです。

以下の方針では、もう少し自由なことができます。整数の集合に対して「\(n\) 以上であって、集合に含まれない最小の整数は何ですか？」という形式のクエリを処理します。

tl; dr

区間を set<pair> で持つやつ。

アイディア

データの持ち方

整数の集合を考えます。例として \(\{-3, -2, 0, 1, 2, 3, 7\}\) を考えましょうか。これを、愚直に管理するのではなく、一続きの整数を区間として管理します。 [-3, -2, 0, 1, 2, 3, 7] ではなく、[(-3, -2), (0, 3), (7, 7)] のようにということですね。

区間の始端と終端をペアで持っておきます。閉区間か半開区間のどちらを選ぶかは状況に応じて好きにするといいと思いますが、ここでは閉区間とします。

これを、順序つき辞書（C++ で言うところの std::set、Rust で言うところの std::collections::BTreeSet）で管理します。順序は、ペアの辞書順で定義されるとします。

クエリ処理

まず、x が集合に含まれるかどうかの判定を先に書いておきます。 x が含まれる区間があれば、(x+1, x+1) 未満で最大の区間なので、辞書でそういう操作をします。必要に応じて、(-inf, -inf) や (+inf, +inf) を番兵として入れておくと楽かもしれません。

x を追加する（かつ x が含まれていない）ときは、挿入されるべき箇所の両隣を見て、x-1 や x+1 があればそれらとくっつけます。上の集合に 4 を加えると [(-3, -2), (0, 4), (7, 7)] に、さらに -1 を加えると [(-3, 4), (7, 7)] になります。

x 以上で含まれない最小要素は、x を含む区間（なければ x が答え）を持ってきて、その終端に 1 加えたものになります。

x を削除するのも考えるとできます。条件を考えて追加の逆っぽいことをします。

実装

貼ると、HHKB 2020 C を解けます。

C++ です。 atcoder.jp

Rust がいいですか。 atcoder.jp

Further Queries

さらに、区間追加クエリもできます。それはそうって感じだね。

ならし対数時間になりますが、「x を追加してね」だけではなく「l 以上 u 以下の整数を追加してね」というのもできます。 {2, 4, 6, 8, ..., n-1} のような集合に「1..=n を追加してね」と言われるような場合では一回の処理は \(O(\log(n))\) 時間ではないですが、ならせば大丈夫です。

あとは、区間削除とかもできます。当然、x を含む区間とかが必要になる問題ではそれも求められます。

こういうのとかが解けますね。

RUQ (for verification)

（追記：2020/11/19）

ここ、mex は関係ないです。verify のための補足です。

この形式で区間の集合を扱うやつを用いて、RUQ を処理できます。配列 \(a\) に対して、次の処理を行います。

区間 \([s, t)\) の値を \(x\) にしてね
\(a_i\) の値を答えてね

答えの上限を \(2^w -1\) とします。リンク先の問題では \(w=31\) です。区間の集合を \(w\) 個用意します。

\(x\) の \(j\) bit 目が \(1\) のとき、\(j\) 個目の集合に \([s, t)\) を追加します。 \(0\) のとき、\(j\) 個目の集合から \([s, t)\) を削除します。

\(a_i\) の値は、「\(j\) 番目の集合が \([i, i]\) を含むなら \(2^j\)、含まないなら \(0\)」の各 \(j\) における総和です。

最悪計算量はクエリあたり \(O(\log(n)\log(w))\) ですが、実際には各集合の要素数は \(n\) より小さいことも多いので、必ずしもこれだけかかるとは限りません。

その他 verify とか使い道とか

（追記：2021/01/08）

いろいろあると思います。思い出したら足します。

ねこちゃん

ねこちゃんなので。