E - Mex and Update

[hxrxchang]

https://atcoder.jp/contests/abc330/tasks/abc330_e

問題概要

数列Aが与えられる。
以下のクエリにQ回対応せよ。

• i, x が与えられるので、A[i] = x に変更する。
• Aのmex(Aに含まれない最小の非負整数)を出力せよ

解き方

N個の数列の中のmexとしてあり得るのはN以下しかないということに気づけるといい。
N <= 2 * 10 ** 5 なので、全列挙できる。

Aの集合をmultisetで管理する。multiSetにしたいのは、後述するmex候補にできるかを判定したり、Aの値を変更するときに変更された値が他にAに残っていなかったらmex候補に追加する、といった処理を高速に行いたいから。
0 < i < n のiでAに存在しないもの集合をmex候補としてSortedSetで管理する。
クエリにたびにAとmex候補を更新して、mex候補の最小値がmexになる。

func solve() {
	in := getInts()
	n, q := in[0], in[1]

	a := getInts()
	aSet := newMultiset[int]()
	for _, v := range a {
		aSet.Add(v)
	}

	mexSet := newSortedSet[int]()
	for i := 0; i <= n; i++ {
		if !aSet.Has(i) {
			mexSet.add(i)
		}
	}

	for i := 0; i < q; i++ {
		in := getInts()
		i, x := in[0]-1, in[1]
		target := a[i]

		// 数列Aから削除
		aSet.Remove(target)
		// 数列Aにその値が他に存在しない場合、mexの候補になる
		if !aSet.Has(target) {
			mexSet.add(target)
		}

		// xを数列Aに追加
		aSet.Add(x)
		a[i] = x
		mexSet.remove(x)

		fmt.Println(mexSet.First().Value())
	}
}

https://atcoder.jp/contests/abc330/submissions/60019230