Mexを計算する
mexとは？"minimum excluded"の略で、集合に含まれない最小の要素のこと
これを計算する方法はだいたい２つくらいある
セグ木
区間をsetで管理するテク
セグ木
区間をsetで管理するテクよりも軽実装
区間minセグ木を作る
実装
追加
計算量: $ O(\log \max A)
$ A_x = \infty
削除
計算量: $ O(\log \max A)
$ A_x = x
取得
計算量: $ O(\log \max A)
$ \min A
結果が$ \inftyになったら最大値+1を返す
取得 $ x \in [l, r)
計算量: $ O(\log \max A)
$ \min \{A_x | l \le x \lt r \}
多重集合にしたい場合は$ xごとにカウントを持つと良い（カウントが$ 0になったら削除、$ 1以上になったら追加）
またはセグ木の要素を$ (\text{値}, \text{個数})にして、演算を、個数が$ 1以上の最小の要素を返すようにする
この方法では$ O(最大値)の空間が必要（オフラインの場合、座圧すれば$ O(N)にできる）
区間をsetで管理するテク
現在持っている区間を順序付き集合で管理する
区間追加とかもできる
だいたい$ O(\log Q)でできる（最大値に依存しない）
別途mapで個数を持つと多重集合にできる