分数: 475 点
问题陈述
给你一个序列 A=(A_1,A_2,\dots,A_N) 长度 N.
回复以下内容 Q 按给出的顺序进行查询。
的 k第一个查询按以下格式给出:
i_k x_k
- 一、改变 A_{i_k} to x_k。此更改将延续到后续查询。
- 然后,打印 \rm{mex} of A.
- 的 \rm{mex} of A 是不包含在中的最小非负整数 总共 A.
约束
- 所有输入值均为整数。
- 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
输入
输入由标准输入按以下格式给出:
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
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
最初,序列 A is (2,0,2,2,1,1,2,5).
此输入为您提供五个查询。
- 第一个查询发生变化 A_4 to 3, 制作 A=(2,0,2,3,1,1,2,5).
- 此时, \rm{mex} of A is 4.
- 第二个查询发生变化 A_4 to 4, 制作 A=(2,0,2,4,1,1,2,5).
- 此时, \rm{mex} of A is 3.
- 第三个查询发生变化 A_6 to 3, 制作 A=(2,0,2,4,1,3,2,5).
- 此时, \rm{mex} of A is 6.
- 第四个查询变化 A_8 to 1000000000, 制作 A=(2,0,2,4,1,3,2,1000000000).
- 此时, \rm{mex} of A is 5.
- 第五个查询变化 A_2 to 1, 制作 A=(2,1,2,4,1,3,2,1000000000).
- 此时, \rm{mex} of A is 0.