A16795. Yet Another MEX Problem
编程题
普及/提高-
知识点
题目描述
给定一个长度为 $n$ 的数组 $a$，以及一个整数 $k$。令 $f(l, r)$ 表示 $\operatorname{mex}(a_l,a_{l+1},\ldots,a_r)$ $^\text{∗}$ 的值。你需要进行如下操作 $n-k+1$ 次：
- 设当前序列长度为 $|a|$。你需要找到一个长度为 $k$ 的区间 $[l, r]$，使得 $\operatorname{max}_{i=1}^{|a|-k+1} f(i, i+k-1) = f(l, r)$。换句话说，你需要在所有长度为 $k$ 的窗口中，选择一个 $\operatorname{mex}$ 最大的窗口 $[l, r]$。如果有多个符合条件的区间 $[l, r]$，可以任选其一。然后，你必须选择一个整数 $i$，满足 $l \leq i \leq r$，并将 $a_i$ 从 $a$ 中删除。也就是说，新的序列将变为 $[a_1, a_2, \ldots, a_{i-1}, a_{i+1}, a_{i+2}, \ldots, a_n]$。
例如，对于数组 $[1,2,0,1,3,0]$ 且 $k=3$，两个可能的 $(l,r)$ 对为 $(1,3)$ 和 $(2,4)$（因为这两个窗口的 $\operatorname{mex}$ 都为 $3$，是所有长度为 $3$ 的窗口中最大的）。因此，你可以在下一个步骤中删除下标 $1,2,3,4$ 之中的任意一个。
经过 $n-k+1$ 次操作后，你会得到一个长度为 $k-1$ 的序列。你的目标是最大化剩余元素的 $\operatorname{mex}$。请输出可能获得的最大 $\operatorname{mex}$。
$^\text{∗}$ 一组整数 $c_1,c_2,\ldots,c_k$ 的 minimum excluded（MEX）定义为集合 $c$ 中未出现的最小非负整数 $x$。
- 设当前序列长度为 $|a|$。你需要找到一个长度为 $k$ 的区间 $[l, r]$，使得 $\operatorname{max}_{i=1}^{|a|-k+1} f(i, i+k-1) = f(l, r)$。换句话说，你需要在所有长度为 $k$ 的窗口中，选择一个 $\operatorname{mex}$ 最大的窗口 $[l, r]$。如果有多个符合条件的区间 $[l, r]$，可以任选其一。然后，你必须选择一个整数 $i$，满足 $l \leq i \leq r$，并将 $a_i$ 从 $a$ 中删除。也就是说，新的序列将变为 $[a_1, a_2, \ldots, a_{i-1}, a_{i+1}, a_{i+2}, \ldots, a_n]$。
例如，对于数组 $[1,2,0,1,3,0]$ 且 $k=3$，两个可能的 $(l,r)$ 对为 $(1,3)$ 和 $(2,4)$（因为这两个窗口的 $\operatorname{mex}$ 都为 $3$，是所有长度为 $3$ 的窗口中最大的）。因此，你可以在下一个步骤中删除下标 $1,2,3,4$ 之中的任意一个。
经过 $n-k+1$ 次操作后，你会得到一个长度为 $k-1$ 的序列。你的目标是最大化剩余元素的 $\operatorname{mex}$。请输出可能获得的最大 $\operatorname{mex}$。
$^\text{∗}$ 一组整数 $c_1,c_2,\ldots,c_k$ 的 minimum excluded（MEX）定义为集合 $c$ 中未出现的最小非负整数 $x$。
输入格式
每组测试包含多个测试用例。第一行为测试用例数 $t$（$1 \le t \le 10^4$）。每组测试的描述如下。
每组测试的第一行包含两个正整数 $n$ 和 $k$（$2\leq k \leq n \leq 2\cdot 10^5$）。
第二行为 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0\leq a_i \leq n$）。
保证所有测试用例的 $n$ 之和不超过 $2\cdot 10^5$。
每组测试的第一行包含两个正整数 $n$ 和 $k$（$2\leq k \leq n \leq 2\cdot 10^5$）。
第二行为 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$0\leq a_i \leq n$）。
保证所有测试用例的 $n$ 之和不超过 $2\cdot 10^5$。
输出格式
输出一个非负整数，表示答案。
输入输出样例
输入 #1
5 3 3 0 0 0 4 2 0 2 1 3 5 3 0 1 2 1 0 6 2 0 1 0 1 2 0 7 5 0 1 2 4 0 3 1
输出 #1
1 1 2 1 4
说明/提示
在第一个测试用例中，我们可以选择区间 $[1,3]$，然后删除 $a_2$ 得到 $[0,0]$。此时操作结束，剩余元素的 $\operatorname{mex}$ 为 $1$。
在第三个测试用例中，我们可以按如下操作：
- 选择 $i=1,j=3$。这是允许的，因为所有长度为 $3$ 的窗口的 $\operatorname{mex}$ 分别为 $3,0,3$，其中区间 $[1,3]$ 的 $\operatorname{mex}$ 为 $3$，为最大值。然后删去 $a_2$，序列变成 $[0,2,1,0]$。
- 选择 $i=2,j=4$。删去 $a_2$，序列变为 $[0,1,0]$。
- 选择 $i=1,j=3$。删去 $a_1$，序列变为 $[1,0]$。操作结束，最终 $\operatorname{mex}$ 为 $2$。
在第三个测试用例中，我们可以按如下操作：
- 选择 $i=1,j=3$。这是允许的，因为所有长度为 $3$ 的窗口的 $\operatorname{mex}$ 分别为 $3,0,3$，其中区间 $[1,3]$ 的 $\operatorname{mex}$ 为 $3$，为最大值。然后删去 $a_2$，序列变成 $[0,2,1,0]$。
- 选择 $i=2,j=4$。删去 $a_2$，序列变为 $[0,1,0]$。
- 选择 $i=1,j=3$。删去 $a_1$，序列变为 $[1,0]$。操作结束，最终 $\operatorname{mex}$ 为 $2$。