AT_abc330_e [ABC330E] 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$ 个查询的答案，输出一个整数。

输入输出样例 #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\leq N,Q\leq 2\times 10^5$
• $0\leq A_i\leq 10^9$
• $1\leq i_k\leq N$
• $0\leq x_k\leq 10^9$

样例解释 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$。

由 ChatGPT 4.1 翻译