题目大意

给定一个序列，每次查询修改其中一项并询问序列中未出现的最小非负整数。

题目思路

map维护序列中每项出现次数，同时用于判断序列中数字的增添与消失

set维护有哪些数字没有出现在序列中，其第一项（最小值）就是查询的答案

序列中没出现的数字有无穷多个，为什么可以用有限的集合来维护呢？经过思考我们得出，在长度为$n$的序列中，$mex \leq n$，所以直接做就好了。

AC代码

#include<bits/stdc++.h>
using namespace std;
map<int, int> mp;
set<int> st;
int a[(int)2e5 + 10];
int main()
{
	int n, q; cin >> n >> q;
	for (int i = 1, x; i <= n; i++)
		cin >> a[i], mp[a[i]] ++;
	for (int i = 0; i <= n; i++)
		if (mp.find(i) == mp.end()) st.insert(i);
	while (q--)
	{
		int i, x; cin >> i >> x;
		mp[a[i]] --;
		if (mp[a[i]] == 0) st.insert(a[i]);
		a[i] = x;
		mp[x] ++;
		if (st.find(x) != st.end()) st.erase(x);
		cout << *st.begin() << endl;
	}
}