Making Mexes

题目描述

给定一个由 $N$ 个非负整数组成的数组 $a$，其中 $a_1, a_2, \dots, a_N$ ($1\le N\le 2\cdot 10^5, 0\le a_i\le N$)。在一次操作中，你可以将 $a$ 的任意一个元素改为任意非负整数。 数组的 mex 定义为数组中不包含的最小非负整数。 对于每个 $i$（从 $0$ 到 $N$，包含端点），计算使得数组 $a$ 的 mex 等于 $i$ 所需的最少操作次数。

输入格式

第一行包含 $N$。 下一行包含 $a_1, a_2, \dots, a_N$。

输出格式

对于每个 $i$（从 $0$ 到 $N$），在新的一行输出对应的最少操作次数。 注意：总是可以使数组 $a$ 的 mex 等于 $0$ 到 $N$ 范围内的任意 $i$。

4
2 2 2 0

1
0
3
1
2

提示

要使 $a$ 的 mex 等于 $0$，我们可以将 $a_4$ 改为 $3$（或任意正整数）。在得到的数组 $[2, 2, 2, 3]$ 中，$0$ 是数组不包含的最小非负整数，因此 $0$ 是该数组的 mex。 要使 $a$ 的 mex 等于 $1$，我们不需要进行任何修改，因为 $1$ 已经是 $a = [2, 2, 2, 0]$ 中不包含的最小非负整数。 要使 $a$ 的 mex 等于 $2$，我们需要修改 $a$ 的前三个元素。例如，我们可以将 $a$ 改为 $[3, 1, 1, 0]$。 SCORING: 输入 2-6：$N\le 10^3$ 输入 7-11：无额外限制。 题目来源：Benjamin Qi

标签: USACO|2025|Bronze

来源

USACO|2025|Bronze