官方题解

题目大意

给定一个序列，进行 $q$ 次操作，每次操作后输出操作后的序列的 $mex$ 。

解题思路

首先，很显然的是，无论进行怎样的操作，一个序列的 $mex$ 一定不会超过 $n$ 。

所以只需要记录和处理小于等于 $n$ 的元素即可，这个过程可以通过桶数组 cnt 和 set 完成，其中桶数组用于记录当前序列中小于 $n$ 的各个元素的个数，set 记录当前这个序列还没有出现过的数，即满足 cnt[i]=0 的数字 $i$ 。最终答案即为 set 中第一个数，输出 *s.begin() 即可。

参考代码

#include <bits/stdc++.h>
using namespace std;
const int N = 1000010;

int n,q;
int a[N];
int cnt[N];
set<int>ust;

int main(){
    cin>>n>>q;
    for(int i=1;i<=n;i++){
        cin>>a[i];
		if(a[i]<=n) cnt[a[i]]++;
    }
    for(int i=0;i<=n;i++){
        if(!cnt[i]){
            ust.insert(i);
        }
    }
    while(q--){ 
        int pos,x;cin>>pos>>x;
        if(a[pos]<=n) {
            cnt[a[pos]]--;
            if(cnt[a[pos]]==0) ust.insert(a[pos]);
        }
        a[pos]=x;
        if(a[pos]<=n) {
            if(cnt[a[pos]]==0) ust.erase(a[pos]);
            cnt[a[pos]]++;
        }
        cout<<*ust.begin()<<endl;
    }
    return 0;
}