06763. USACO·打造MEX数组 · 林老师的题库

题目描述

给定一个包含 $N$ 个非负整数的数组 $a$ ， $a_{1}, a_{2}, \dots, a_{N}$ （ $1 \leq N \leq 2 \cdot 1 0^{5}$ ， $0 \leq a_{i} \leq N$ ）。在一次操作中，你可以将 $a$ 的任一元素修改为任意非负整数。

一个数组的 mex 是它不包含的最小非负整数。对于范围 $0$ 到 $N$ 内的每一个 $i$ ，计算使 $a$ 的 mex 等于 $i$ 所需要的最小操作次数。

输入的第一行包含 $N$ 。

以下一行包含 $a_{1}, a_{2}, \dots, a_{N}$ 。

对于范围 $0$ 到 $N$ 内的每一个 $i$ 输出一行，包含对于 $i$ 的最小操作次数。注意， $a$ 的 mex 对于范围 $0$ 到 $N$ 内的任意 $i$ 值都是可以通过修改取到的。

输入

4
2 2 2 0

输出

【样例解释】

为使 $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]$ 。
测试点 7-11：没有额外限制。

【数据规模与约定】

供题：Benjamin Qi