0559 Atcoder ABC 330 - Mex and Update | OJ题库

题目详情

返回题库

题目描述

有一个长度为N的序列a=（A1 ,A 2 ,…,A N )。按照给定的顺序查询。

第k个查询以以下格式给出：

 $ik_{k}$   $xk_{k}$

首先，把Aik更新成Xk .
然后，打印A的mex。
- A的mex是集合A中不存在的最小非负数

输入描述

输入格式如下：

N Q

A1 A2 A3 A4 ,....AN

i1 x1

i2 x2

i3 x3

...

ik xk

数据范围：

1≤N,Q≤2×10^5
0≤Ai≤10^9
1≤ik≤N
0≤xk≤10^9

输出描述

输出k行：每行一个整数代表该次查询的结果

测试样例

样例支持多行内容展示

样例1

输入

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

输出

4
3
6
5
0

最初，序列A是（2,0,2,1,1,2,5）。
第一个查询更改A4到到3，使得A=（2,0,2,3,1,2,5）。此时，A的mex为4。
第二个查询更改A4到到4，使得A=（2,0,2,4,1,2,5）。此时，A的mex为3。
第三个查询更改A6到到3，使得A=（2,0,2,4,1,3,2,5）。此时，A的mex为6。
第四个查询更改A8到到1000000000，使得A=（2,0,2,4,1,3,2，1000000000）。此时，A的mex为5。
第五个查询更改A2变变为1，使得A=（2,1,2,4,1,3,21000000000）。此时，A的mex为0。

提交前会先自动运行样例。只有样例全部通过，才会进入后端正式判题。

欢迎回来

选择你的下一步

题目详情

题目描述

输入描述

输出描述

测试样例