CFCF2183B.Yet Another MEX Problem

普及/提高-

通过率：0%

AC君温馨提醒

该题目为【codeforces】题库的题目，您提交的代码将被提交至codeforces进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

给定一个长度为 $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$ 。

输入格式

每组测试包含多个测试用例。第一行为测试用例数 $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$ 。

输出格式

输出一个非负整数，表示答案。

输入输出样例

输入#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,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$ 。

首页