[ABC330E] Mex and Update

题面翻译

给定一个序列，支持单点修改，每次修改后输出全局 $\mathrm{mex}$。

一个序列的 $\mathrm{mex}$ 定义为，序列中最小的没有出现过的非负整数。

题目描述

長さ $ N $ の数列 $ A=(A_1,A_2,\dots,A_N) $ が与えられます。
以下の $ Q $ 個のクエリに、与えられる順番で対応してください。

$ k $ 番目のクエリは以下の形式で与えられます。

$ i_k $ $ x_k $

• まず、 $ A_{i_k}\ =\ x_k $ と変更する。この変更は以降のクエリにも引き継がれる。
• その後、 $ A $ の $ \rm{mex} $ を出力する。
  • $ A $ の $ \rm{mex} $ とは、 $ A $ に含まれない最小の非負整数を指す。

输入格式

入力は以下の形式で標準入力から与えられる。

$ N $ $ Q $ $ A_1 $ $ A_2 $ $ \dots $ $ A_N $ $ i_1 $ $ x_1 $ $ i_2 $ $ x_2 $ $ \vdots $ $ i_Q $ $ x_Q $

输出格式

全体で $ Q $ 行出力せよ。
そのうち $ k $ 行目には $ k $ 番目のクエリに対する答えを整数として出力せよ。

样例 #1

样例输入 #1

8 5
2 0 2 2 1 1 2 5
4 3
4 4
6 3
8 1000000000
2 1

样例输出 #1

4
3
6
5
0

提示

制約

• 入力は全て整数
• $ 1\ \le\ N,Q\ \le\ 2\ \times\ 10^5 $
• $ 0\ \le\ A_i\ \le\ 10^9 $
• $ 1\ \le\ i_k\ \le\ N $
• $ 0\ \le\ x_k\ \le\ 10^9 $

Sample Explanation 1

最初、数列 $ A $ は $ (2,0,2,2,1,1,2,5) $ です。 この入力では、 $ 5 $ つのクエリを処理します。 - $ 1 $ 番目のクエリで $ A_4\ =\ 3 $ と変更し、 $ A=(2,0,2,3,1,1,2,5) $ となりました。 - この時点で、 $ A $ の $ \rm{mex} $ は $ 4 $ です。 - $ 2 $ 番目のクエリで $ A_4\ =\ 4 $ と変更し、 $ A=(2,0,2,4,1,1,2,5) $ となりました。 - この時点で、 $ A $ の $ \rm{mex} $ は $ 3 $ です。 - $ 3 $ 番目のクエリで $ A_6\ =\ 3 $ と変更し、 $ A=(2,0,2,4,1,3,2,5) $ となりました。 - この時点で、 $ A $ の $ \rm{mex} $ は $ 6 $ です。 - $ 4 $ 番目のクエリで $ A_8\ =\ 1000000000 $ と変更し、 $ A=(2,0,2,4,1,3,2,1000000000) $ となりました。 - この時点で、 $ A $ の $ \rm{mex} $ は $ 5 $ です。 - $ 5 $ 番目のクエリで $ A_2\ =\ 1 $ と変更し、 $ A=(2,1,2,4,1,3,2,1000000000) $ となりました。 - この時点で、 $ A $ の $ \rm{mex} $ は $ 0 $ です。

思路：直接操作会超时，我们可以统计没有出现的数，用set存储，最小的那个数就是每个的答案

AC代码：

#include<bits/stdc++.h>using namespace std;typedef long long ll;
typedef pair<int, int>PII;
const int MOD = 998244353;
const int N = 4e5 + 10;int dx[] = {0, 0, 1, -1};
int dy[] = {1, -1, 0, 0};ll a[N];
//我们可以储存没有出现的数
int n, k;
int b[N];
set<int>se;
int main()
{cin >> n >> k;for(int i = 1; i <= n; i ++) {cin >> a[i];if(a[i] >= 4e5) continue;b[a[i]] ++;}for(int i = 0; i <= n * 2; i ++){if(!b[i]) se.insert(i);//记录没有出现的数，注意边界}while(k --){int x, c;cin >> x >> c;if(a[x] <= n * 2)b[a[x]] --;if(c <= n * 2)b[c] ++;if(a[x] <= n * 2){if(b[a[x]] == 0) se.insert(a[x]);//变为没有出现的数了}if(c <= n * 2){if(se.count(c)) se.erase(c);//出现了			}a[x] = c;cout << *se.begin() << endl;}
}