Add and Mex

题目描述

你得到一个长度为 $N$ 的整数序列 $A=(A_1,A_2,\ldots,A_N)$。 执行以下操作 $M$ 次：

对于每个 $i\ (1\leq i \leq N)$，将 $i$ 加到 $A_i$ 上。然后，找出不包含在 $A$ 中的最小非负整数。

输入格式

输入从标准输入按以下格式给出： $N$ $M$ $A_1$ $A_2$ $\ldots$ $A_N$

输出格式

输出 $M$ 行。 第 $i$ 行 $(1\leq i \leq M)$ 应包含在第 $i$ 次操作后不包含在 $A$ 中的最小非负整数。

3 3
-1 -1 -6

2
2
0

5 6
-2 -2 -5 -7 -15

1
3
2
0
0
0

提示

$1\leq N,M \leq 2\times 10^5$ $-10^9\leq A_i\leq 10^9$ 输入中的所有数值均为整数。第 $1$ 次操作使序列 $A$ $(-1 + 1, -1 +2 ,-6+3) = (0,1,-3).$ 不包含在 $A$ 中的最小非负整数是 $2$。 第 $2$ 次操作使序列 $A$ $(0 + 1, 1 +2 ,-3+3) = (1,3,0).$ 不包含在 $A$ 中的最小非负整数是 $2$。 第 $3$ 次操作使序列 $A$ $(1 + 1, 3 +2 ,0+3) = (2,5,3).$ 不包含在 $A$ 中的最小非负整数是 $0$.

标签: AtCoder|abc272E

来源

AtCoder|abc272E