当前位置：首页 > article >正文

[ABC330E] Mex and Update

article 2024/11/14 23:21:44

[ABC330E] Mex and Update

题面翻译

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

一个序列的 $\operatorname{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

提示

制約

入力は全て整数
$ 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;
	}
}