AT_abc194_e [ABC194E] Mex Min

题目描述

定义 $\mathrm{mex}(x_1,\ x_2,\ x_3,\ \dots,\ x_k)$ 为不包含在 $x_1,\ x_2,\ x_3,\ \dots,\ x_k$ 中的最小非负整数。

给定一个长度为 $N$ 的整数序列 $A = (A_1,\ A_2,\ A_3,\ \dots,\ A_N)$。

对于所有满足 $0 \le i \le N - M$ 的整数 $i$，计算 $\mathrm{mex}(A_{i+1},\ A_{i+2},\ A_{i+3},\ \dots,\ A_{i+M})$，在这 $N - M + 1$ 个值中，求出最小值。

输入格式

输入以以下格式从标准输入读入：

$N$ $M$ $A_1$ $A_2$ $A_3$ $\cdots$ $A_N$

输出格式

输出答案。

输入输出样例 #1

输入 #1

3 2
0 0 1

输出 #1

1

输入输出样例 #2

输入 #2

3 2
1 1 1

输出 #2

0

输入输出样例 #3

输入 #3

3 2
0 1 0

输出 #3

2

输入输出样例 #4

输入 #4

7 3
0 0 1 2 0 1 0

输出 #4

2

说明/提示

限制条件

• $1 \le M \le N \le 1.5 \times 10^6$
• $0 \le A_i < N$
• 输入中的所有值均为整数

样例解释 1

• 当 $i = 0$ 时：$\mathrm{mex}(A_{i+1},\ A_{i+2}) = \mathrm{mex}(0, 0) = 1$
• 当 $i = 1$ 时：$\mathrm{mex}(A_{i+1},\ A_{i+2}) = \mathrm{mex}(0, 1) = 2$ 因此，$1$ 和 $2$ 中的最小值为 $1$，答案为 $1$。

样例解释 2

• 当 $i = 0$ 时：$\mathrm{mex}(A_{i+1},\ A_{i+2}) = \mathrm{mex}(1, 1) = 0$
• 当 $i = 1$ 时：$\mathrm{mex}(A_{i+1},\ A_{i+2}) = \mathrm{mex}(1, 1) = 0$ 因此答案为 $0$。

样例解释 3

• 当 $i = 0$ 时：$\mathrm{mex}(A_{i+1},\ A_{i+2}) = \mathrm{mex}(0, 1) = 2$
• 当 $i = 1$ 时：$\mathrm{mex}(A_{i+1},\ A_{i+2}) = \mathrm{mex}(1, 0) = 2$ 因此答案为 $2$。

由 ChatGPT 4.1 翻译