← 返回题目列表

AtCoder · abc330_e

H. 墨西哥和更新

中文机器翻译题面 查看原题

分数: 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.