AT_abc272_e [ABC272E] 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$ 中不包含的最小非负整数。

输入输出样例 #1

输入 #1

3 3
-1 -1 -6

输出 #1

2
2
0

输入输出样例 #2

输入 #2

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

输出 #2

1
3
2
0
0
0

说明/提示

限制条件

• $1\leq N,M \leq 2\times 10^5$
• $-10^9\leq A_i\leq 10^9$
• 输入均为整数

样例解释 1

第 $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$。

由 ChatGPT 4.1 翻译