\(\rm{mex}\) の重要な性質として、長さ \(N\) の非負整数列の \(\rm{mex}\) は \(0\) 以上 \(N\) 以下です。
証明: 数列の長さは \(N\) ですが、 \(0\) 以上 \(N\) 以下の整数は \(N+1\) 個存在します。 このことから、 \(0\) 以上 \(N\) 以下の整数のうち含まれないものが少なくともひとつ存在することが分かります。

このことから、数列 \(A\) のうち \(N+1\) 以上のものは無視していい ( 「全て \(N+1\) であると取り扱う」「処理を行わない」などの方法で対処することができます ) ことが分かります。

クエリを処理していく段階で、 \(\rm{bk}\)\([i] = \) ( \(A\) 中に含まれる \(i\) の個数 ) を常に保持していくことを考えます。見つけるべきは \(\rm{bk}\)\([k]=0\) なる最小の \(k\) です。

これは、以下の手続きで発見できます。

• まず、「整数を追加する」「指定した整数を削除する」「最小値を取り出す」ことができるデータ構造 \(s\) を用意する。 ( 例えば、C++で set を使ったり、 ACL の segtree の max_right を応用したりして実現できます。 )
• 次に、 \(\rm{bk}\) の初期値を計算する。
  • このとき、 \(\rm{bk}\)\([k]=0\) なる \(k\) を全て求め、 \(s\) に入れる。
• 各クエリの処理は以下の手順で行う。
  • まず、更新前の \(A_{i_k}\) について、 \(\rm{bk}\)\([A_{i_K}]\) から \(1\) 減算する。
    • このとき、\(\rm{bk}\)\([A_{i_K}]\) が \(0\) となれば、 \(s\) に \(A_{i_K}\) を追加する。
  • \(A_{i_k}\) を \(x_k\) に更新する。
  • 更新後の \(A_{i_k}\) について、 \(\rm{bk}\)\([A_{i_K}]\) に \(1\) 加算する。
    • このとき、\(\rm{bk}\)\([A_{i_K}]\) が加算前に \(0\) であったなら、 \(s\) から \(A_{i_K}\) を削除する。
  • この時点での \(s\) に含まれる最小値が、このクエリまでの処理を終えた時点での答えになる。

実装例1 (C++):

#include<bits/stdc++.h>

using namespace std;

int main(){
  int n,q;
  cin >> n >> q;
  vector<int> bk(n+1,0);
  vector<int> a(n);
  for(int i=0;i<n;i++){
    cin >> a[i];
    if(a[i]<=n){
      bk[a[i]]++;
    }
  }
  set<int> st;
  for(int i=0;i<=n;i++){
    if(bk[i]==0){st.insert(i);}
  }
  while(q>0){
    q--;
    int i,x;
    cin >> i >> x;
    i--;
    if(a[i]<=n){
      bk[a[i]]--;
      if(bk[a[i]]==0){st.insert(a[i]);}
    }
    a[i]=x;
    if(a[i]<=n){
      if(bk[a[i]]==0){st.erase(a[i]);}
      bk[a[i]]++;
    }
    cout << (*st.begin()) << "\n";
  }
  return 0;
}

実装例2 (C++):

#include<bits/stdc++.h>
#include<atcoder/segtree>

using namespace std;
using namespace atcoder;

int op(int a,int b){return min(a,b);}
int e(){return 1e9;}
bool f(int x){return (x>0);}

int main(){
  int n,q;
  cin >> n >> q;
  vector<int> bk(n+1,0);
  vector<int> a(n);
  for(int i=0;i<n;i++){
    cin >> a[i];
    if(a[i]<=n){bk[a[i]]++;}
  }
  segtree<int,op,e> seg(bk);
  for(int i=0;i<q;i++){
    int p,x;
    cin >> p >> x;
    p--;
    if(a[p]<=n){
      seg.set(a[p],seg.get(a[p])-1);
    }
    a[p]=x;
    if(a[p]<=n){
      seg.set(a[p],seg.get(a[p])+1);
    }
    cout << seg.max_right<f>(0) << "\n";
  }
  return 0;
}