解法
vector \(a\) に対して，\(mex(a)\) の求め方を考える． \(N := \vert a \vert\)とおく． まず， \(0 \leq mex(a) \leq N\) であることに注意する． \(a\)の元のうち，\(N\)以上の物は無視して良いことになる．
\(mex(a)\)を答えるためには， \(a\)の中に\(x\)が \(0\) 個である \(0 \leq x < N\) の集合 \(s\) も持っておけば十分．
\(a\)の元を書き換えるクエリが来るので， 書き変わったときに \(s\) がどの様に変化するかを 得られれば十分． よって， \(0 \leq x < N\) となる各 \(x\)に対して， \(a\)の中に\(x\)が何個あるかを持っておけば十分． クエリの基本は，差分を更新して高速化すること．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n, q;
cin >> n >> q;
vll cnt(n);
vll a(n);
rep(i,n){
cin >> a[i];
if(a[i] < n) cnt[a[i]]++;
}
set<ll> zero;
rep(i,n){
if(cnt[i]==0) zero.insert(i);
}
zero.insert(n);
rep(qi,q){
ll i,x; cin >> i >> x;
--i;
if(a[i] < n) {
cnt[a[i]]--;
if(cnt[a[i]]==0) zero.insert(a[i]);
}
if(x < n){
cnt[x]++;
if(cnt[x]!=0) zero.erase(x);
}
a[i] = x;
assert(zero.size());
cout << *(zero.begin()) << endl;
}
return 0;
}
