← 返回题目列表

Codeforces · 1294/D

D. MEX 最大化

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

回想一下,数组的 MEX 是不属于该数组的最小非负整数。示例:

- 对于数组 $$$[0, 0, 1, 0, 2]$$$ MEX 等于 $$$3$$$,因为数字 $$$0、1$$$ 和 $$$2$$$ 出现在数组中,$$$3$$$ 是数组中未出现的最小非负整数;
- 对于数组 $$$[1, 2, 3, 4]$$$ MEX 等于 $$$0$$$ 因为 $$$0$$$ 是数组中未出现的最小非负整数;
- 对于数组 $$$[0, 1, 4, 3]$$$ MEX 等于 $$$2$$$,因为 $$$2$$$ 是数组中未出现的最小非负整数。

给定一个空数组 $$$a=[]$$$ (换句话说,一个零长度数组)。您还将获得一个正整数 $$$x$$$。

您还会收到 $$$q$$$ 查询。第 $$$j$$$ 查询由一个整数 $$$y_j$$$ 组成,意味着您必须将一个元素 $$$y_j$$$ 追加到数组中。查询后数组长度增加$$$1$$$。

一步操作中,您可以选择任意索引 $$$i$$$ 并设置 $$$a_i := a_i + x$$$ 或 $$$a_i := a_i - x$$$ (即将数组的任意元素增加或减少 $$$x$$$)。唯一的限制是 $$$a_i$$$ 不能变为负数。由于最初数组是空的,因此您只能在第一个查询之后执行移动。

如果您可以执行任意数量的此类操作(甚至可以对一个元素执行多次该操作),则必须最大化数组的 MEX(排除最小值)。

您必须在每个 $$$q$$$ 查询之后找到答案(即第 $$$j$$$ 个答案对应于长度为 $$$j$$$ 的数组)。

在每次查询之前操作都会被丢弃。 IE。第 $$$j$$$ 个查询之后的数组 $$$a$$$ 等于 $$$[y_1, y_2, \dots, y_j]$$$。

输入

输入的第一行包含两个整数 $$$q, x$$$ ($$$1 \le q, x \le 4 \cdot 10^5$$$) — 查询数量和 $$$x$$$ 的值。

接下来的 $$$q$$$ 行描述查询。第 $$$j$$$ 查询由一个整数 $$$y_j$$$ ($$$0 \le y_j \le 10^9$$$) 组成,意味着您必须将一个元素 $$$y_j$$$ 追加到数组中。

输出

在每次查询后打印初始问题的答案 — 对于查询 $$$j$$$,在第一个 $$$j$$$ 查询后打印 MEX 的最大值。请注意,查询是相关的(每次查询后数组都会更改),但查询之间的操作是独立的。

示例

输入 #1

7 3
0
1
2
2
0
0
10

输出 #1

1
2
3
3
4
4
7

输入 #2

4 3
1
2
1
2

输出 #2

0
0
0
0

注意

在第一个示例中:

- 第一次查询后,数组为 $$$a=[0]$$$:您不需要执行任何操作,最大可能的 MEX 为 $$$1$$$。
- 第二次查询后,数组为 $$$a=[0, 1]$$$:您不需要执行任何操作,最大可能的 MEX 为 $$$2$$$。
- 第三次查询后,数组为 $$$a=[0, 1, 2]$$$:您不需要执行任何操作,最大可能的 MEX 为 $$$3$$$。
- 第四次查询后,数组为 $$$a=[0, 1, 2, 2]$$$:您不需要执行任何操作,最大可能的 MEX 为 $$$3$$$ (您不能通过操作使其更大)。
- 第五次查询后,数组为 $$$a=[0, 1, 2, 2, 0]$$$:可以执行 $$$a[4] := a[4] + 3 = 3$$$。数组更改为 $$$a=[0, 1, 2, 2, 3]$$$。现在 MEX 是最大可能的,等于 $$$4$$$。
- 第六次查询后,数组为 $$$a=[0, 1, 2, 2, 0, 0]$$$:可以执行 $$$a[4] := a[4] + 3 = 0 + 3 = 3$$$。数组更改为 $$$a=[0, 1, 2, 2, 3, 0]$$$。现在 MEX 是最大可能的,等于 $$$4$$$。
- 第七次查询后,数组为 $$$a=[0, 1, 2, 2, 0, 0, 10]$$$。您可以执行以下操作: $$$a[3] := a[3] + 3 = 2 + 3 = 5$$$、$$$a[4] := a[4] + 3 = 0 + 3 = 3$$$、$$$a[5] := a[5] + 3 = 0 + 3 = 3$$$、$$$a[5] := a[5] + 3 = 3 + 3 = 6$$$, $$$a[6] := a[6] - 3 = 10 - 3 = 7$$$, $$$a[6] := a[6] - 3 = 7 - 3 = 4$$$。 生成的数组将为 $$$a=[0, 1, 2, 5, 3, 6, 4]$$$。现在 MEX 是最大可能的,等于 $$$7$$$。