MEXをset<int>から二分探索しようとして失敗した E - Mex and Update

問題

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

考察 (WA)

• 1個以上存在する値をsetで管理して、そこからMEXを高速に求めればいいな
• set内はソートされているのだから二分探索できるだろう
• ということで下記のようなsetを入力としてMEXを返す関数を書いて提出→TLE

using ll = long long;
ll find_mex(set<ll>& se){
  if(se.count(0)==0)return 0;
  ll left=0; // ここまでは値が詰まっている (0,1,2,...)
  ll right=se.size(); // ここまで詰まっていることはない
  while(right-left>1){
    ll center = (left+right)/2;
    auto it = se.lower_bound(center);
    if(it!=se.end() && *it==center && distance(se.begin(),it)==center){
      left=center;
    }else{
      right=center;
    }
  }
  return right;
}

• TLE https://atcoder.jp/contests/abc330/submissions/48478980
• setのdistanceが遅いことが原因。linked listのように1つ1つ辿って距離算出しているのだろう

AC

• 解説と同様に、個数が0である値をsetで持つ方針で解くと、set.begin()を呼ぶだけなのでACします
• AC https://atcoder.jp/contests/abc330/submissions/48479187

int main(){
    cin.tie(0);
    ios::sync_with_stdio(false);

    // input
    ll N,Q;
    cin>>N>>Q;

    map<ll,ll> mp;
    VI A(N);
    rep(i,N){
      ll a;cin>>a;
      A[i]=a;
      mp[a]++;
    }

    set<ll> se;
    rep(i,200200){
      if(mp[i]==0)se.insert(i);
    }

    rep(_,Q){
      ll i,x;cin>>i>>x;i--;
      if(A[i]!=x){
        // 減らす
        ll prev = A[i];
        mp[prev]--;
        if(mp[prev]==0)se.insert(prev);

        // 増やす
        A[i]=x;
        mp[x]++;
        if(mp[x]==1){
          se.erase(x);
        }
      }
      ll mex = *se.begin();
      p(mex);
    }

    return 0;
}