abc330E 单点更新后的Mex

题面：给定长为n的数组A，有q组询问，每次将A[i]修改为x[i]，输出每次修改后A的mex值。
范围：n,q<2E5; A[i],x[i]<1E9

思路：注意到，长度为n的数组，其mex值最大为n。因此，用set维护0~n中没有出现在A中的数，同时用map维护A中各数的现次数。

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define rep(i,a,b) for(int i=a; i<=b; i++)
#define per(i,a,b) for(int i=b; i>=a; i--)

const int N = 200005;
int n, q, A[N];
set<int> nouse;
map<int,int> cnt;
void solve() {
    cin >> n >> q;
    rep(i,0,n) nouse.insert(i);
    rep(i,1,n) {
        cin >> A[i];
        if (A[i] <= n) {
            cnt[A[i]] += 1;
            nouse.erase(A[i]);
        }
    }
    auto del = [&](int x) {
        cnt[x] -= 1;
        if (cnt[x] == 0) {
            nouse.insert(x);
        }
    };
    auto add = [&](int x) {
        if (cnt[x] == 0) {
            nouse.erase(x);
        }
        cnt[x] += 1;
    };
    while (q--) {
        int i, x;
        cin >> i >> x;
        del(A[i]);
        add(x);
        A[i] = x;
        cout << *nouse.begin() << "\n";
    }
}

signed main() {
    cin.tie(0)->sync_with_stdio(0);
    int t = 1;
    while (t--) solve();
    return 0;
}