[ABC330] E - Mex and Update

[Q] E - Mex and Update

考察
1, mexを求めるときは大体set。
2. setに初期値{0,1,2,3,…}を入れる。
3. 値を使用したらsetからerase()。
4. 値を復元したらsetにinsert()。
5. 答えは常にset.begin()

実装

int main() {
  cincout();
  ll N, Q;
  cin >> N >> Q;
  vector<ll> A(N);
  map<ll, ll> mp;
  rep(i, N){
    cin >> A[i];
    mp[A[i]]++;
  }

  set<ll> S;
  // 初期入れ
  rep(i, N + 1){
    if (mp.count(i) == 0) S.insert(i);
  }
  while(Q--){
    ll i, x;
    cin >> i >> x;
    --i;
    mp[A[i]]--;
    if (mp[A[i]] == 0) S.insert(A[i]); // 未使用ならsetに復元
    A[i] = x;
    mp[A[i]]++;
    if (mp[A[i]] == 1) S.erase(A[i]); // 使用するならsetから削除
    cout << *S.begin() << endl;
  }  
}

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