CF1468H K and Medians

我们将一个长度为奇数的序列 $s$ 的中位数定义为：将 $s$ 按非递减顺序排序后，位于中间位置的数。例如，设 $s = [1, 2, 5, 7, 2, 3, 12]$，排序后得到序列 $[1, 2, 2, \underline{3}, 5, 7, 12]$，其中位数为 $3$。 你有一个由 $n$ 个整数 $[1, 2, \dots, n]$ 组成的序列，以及一个奇数 $k$。 每一步，你可以从序列中任选 $k$ 个元素，并删除这 $k$ 个元素中除中位数以外的所有元素。这些元素不要求连续（可以有间隔）。 例如，若你有序列 $[1, 2, 3, 4, 5, 6, 7]$（即 $n=7$），且 $k=3$，那么第一步可以有以下几种选择： - 选择 $[1, \underline{2}, 3]$，$2$ 是它们的中位数，因此 $2$ 不被删除，结果序列为 $[2, 4, 5, 6, 7]$； - 选择 $[2, \underline{4}, 6]$，$4$ 是它们的中位数，因此 $4$ 不被删除，结果序列为 $[1, 3, 4, 5, 7]$； - 选择 $[1, \underline{6}, 7]$，$6$ 是它们的中位数，因此 $6$ 不被删除，结果序列为 $[2, 3, 4, 5, 6]$； - 还有其他多种选择。 你可以进行零次或多次操作。请判断，经过若干次操作后，能否得到序列 $b_1, b_2, \dots, b_m$？ 共有 $t$ 组测试数据。请分别独立解决每组测试数据。

第一行包含一个整数 $t$（$1 \le t \le 1000$），表示测试数据组数。 每组测试数据的第一行包含三个整数 $n$、$k$ 和 $m$（$3 \le n \le 2 \cdot 10^5$；$3 \le k \le n$；$k$ 为奇数；$1 \le m < n$），分别表示初始序列的长度、每次操作选择的元素个数以及目标序列的长度。 每组测试数据的第二行包含 $m$ 个整数 $b_1, b_2, \dots, b_m$（$1 \le b_1 < b_2 < \dots < b_m \le n$），表示希望得到的目标序列，按升序给出。 保证所有测试数据中 $n$ 的总和不超过 $2 \cdot 10^5$。

对于每组测试数据，如果可以得到目标序列 $b$，输出 YES；否则输出 NO。你可以用任意大小写字母输出（如 YES, Yes, yes, yEs 都视为正解）。

在第一个测试用例中，你有序列 $[1, 2, 3]$。由于 $k=3$，你只能选择全部元素 $[1, \underline{2}, 3]$，中位数为 $2$。因此，删除所有被选元素中除中位数外的元素后，得到序列 $[2]$。换句话说，无法得到目标序列 $b=[1]$。 在第二个测试用例中，你有序列 $[1, 2, 3, 4, 5, 6, 7]$，一种最优策略如下： 1. 选择 $k=3$ 个元素 $[2, \underline{3}, 4]$，只保留中位数，得到序列 $[1, 3, 5, 6, 7]$； 2. 选择 $3$ 个元素 $[3, \underline{5}, 6]$，只保留中位数，得到目标序列 $[1, 5, 7]$； 在第四个测试用例中，你有序列 $[1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13]$。你可以选择 $k=7$ 个元素 $[2, 4, 6, \underline{7}, 8, 10, 13]$，只保留中位数，得到目标序列 $b$。 由 ChatGPT 4.1 翻译