CF2162E Beautiful Palindromes

我们称一个长度为 $m$ 的数组 $[b_1, b_2, \dots, b_m]$ 为回文数组，当且仅当满足以下条件： - 对所有 $1 \le i \le m$，都有 $b_i = b_{m-i+1}$。 换句话说，如果一个数组正着和反着读都是一样的，那么它就是回文数组。 你现在有一个包含 $n$ 个整数的数组 $[a_1, a_2, \dots, a_n]$，其中 $1 \le a_i \le n$，以及一个整数 $k$。 你需要恰好进行 $k$ 次如下操作： - 选择一个整数 $x$，其中 $1 \le x \le n$， - 将 $x$ 添加到数组 $a$ 的末尾。 你的目标是，使得最终得到的新数组中回文子数组 $^{\ast}$ 的总数最少。 请输出每次操作中你选择添加的 $k$ 个整数，按照添加顺序给出。 $^{\ast}$ 若数组 $b$ 能够通过从数组 $a$ 的开头删除若干（可以为零或全部）元素，并从末尾删除若干（可以为零或全部）元素得到，那么 $b$ 是 $a$ 的子数组。特别地，数组本身也是它的子数组。

输入的第一行为一个整数 $t$（$1 \le t \le 10^4$），表示测试用例的数量。 每个测试用例第一行为两个整数 $n$ 和 $k$（$3 \le n \le 2\cdot10^5, 1 \le k \le n$），表示数组 $a$ 的长度以及需要添加的操作次数。 每个测试用例的第二行为 $n$ 个整数 $a_1, a_2, \ldots, a_n$（$1 \le a_i \le n$），表示数组 $a$ 的元素。 保证所有测试用例中 $n$ 的总和不超过 $2\cdot10^5$。

对于每个测试用例，输出你每次操作选择的 $k$ 个整数，按照添加顺序给出，使得最终数组中回文子数组的总数最小。 如果存在多种解法，可以输出任意一种。

对于第一个测试用例，如果我们在数组末尾添加 $2$，则 $a$ 变为 $[1, 3, 3, 4, 2]$。这时 $a$ 一共有 $6$ 个回文子数组——$[1]$、$[3]$、$[3]$、$[4]$、$[2]$、$[3, 3]$。 由 ChatGPT 5 翻译