Mex and Update

题目描述

你被给定一个长度为 $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$ 个查询的答案，作为一个整数。

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

提示

所有输入值均为整数。 $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$最初，序列 $A$ 为 $(2,0,2,2,1,1,2,5)$。
该输入给出五个查询。

第一个查询将 $A_4$ 改为 $3$，使得 $A=(2,0,2,3,1,1,2,5)$。 此时，$A$ 的 $\rm{mex}$ 为 $4$。

第二个查询将 $A_4$ 改为 $4$，使得 $A=(2,0,2,4,1,1,2,5)$。 此时，$A$ 的 $\rm{mex}$ 为 $3$。

第三个查询将 $A_6$ 改为 $3$，使得 $A=(2,0,2,4,1,3,2,5)$。 此时，$A$ 的 $\rm{mex}$ 为 $6$。

第四个查询将 $A_8$ 改为 $1000000000$，使得 $A=(2,0,2,4,1,3,2,1000000000)$。 此时，$A$ 的 $\rm{mex}$ 为 $5$。

第五个查询将 $A_2$ 改为 $1$，使得 $A=(2,1,2,4,1,3,2,1000000000)$。 此时，$A$ 的 $\rm{mex}$ 为 $0$。

标签: AtCoder|abc330E

来源

AtCoder|abc330E