← 返回题目列表

Codeforces · 2124/D

D. 制作一个回文

中文机器翻译题面 查看原题

给定一个大小为 $$$n$$$ 的数组 $$$a$$$ 和一个整数 $$$k$$$。您可以多次执行以下操作:

  • 选择两个整数 $$$l$$$ 和 $$$r$$$ $$$(1 \le l \le r \le |a|)$$$,使得 $$$r-l+1 \geq k$$$。
  • 然后,选择一个索引 $$$i$$$,使得 $$$l\leq i \leq r$$$ 其中 $$$a_i$$$ 是子数组 $$$[a_l,a_{l+1},\ldots,a_r]$$$ 中的第 $$$k$$$ 个最小数字。如果有多个可能的$$$i$$$,您可以选择任何一个。例如,考虑 $$$a = [1, 2, 2, 1, 3],l = 1,r = 5$$$ 和 $$$k = 3$$$,$$$i$$$ 的可能候选者是索引 $$$2$$$ 和 $$$3$$$。
  • 然后,从 $$$a$$$ 中删除 $$$a_i$$$,连接数组的其余部分。

确定在任意次数的运算后是否可以获得回文数组$$$^{\text{*}}$$$。请注意,空数组被视为回文数组。

$$$^{\text{*}}$$$数组 $$$b=[b_1,b_2,\ldots,b_m]$$$ 是一个回文,如果对于每个 $$$1 \leq i \leq m$$$,$$$b_i=b_{m+1-i}$$$。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

第一行包含两个整数 $$$n$$$ 和 $$$k$$$ ($$$1 \leq k \leq n \leq 2\cdot 10^5$$$)。

第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \leq a_i \leq n$$$) — 表示数组 $$$a$$$。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$2\cdot 10^5$$$。

输出

对于每个测试用例,输出 是 如果可以创建回文,并且 NO 否则。您可以以任何大小写(上或下)输出。例如,字符串 “是”, “是”, “是”,和 “是” 将被视为积极响应。

示例

输入
复制

8
5 3
5 4 3 4 5
4 1
1 1 2 1
6 6
2 3 4 5 3 2
5 4
5 2 4 3 1
8 5
4 7 1 2 3 1 3 4
5 4
1 2 1 2 2
3 3
1 2 2
4 4
2 1 2 2

输出
复制

YES
YES
YES
NO
NO
YES
NO
YES

注意

在第一个测试用例中,$$$a$$$ 已经是回文。

在第二个测试用例中,我们可以执行如下两个操作: $$$[\mathbf{1,1},2,1]\rightarrow [1,\mathbf{2},1]\rightarrow[1,1]$$$

在第三个测试用例中,我们可以执行如下一项操作:$$$[\mathbf{2,3,4,5,3,2}]\rightarrow[2,3,4,3,2]$$$。

在第四个和第五个测试用例中,可以证明无论使用什么操作都不可能创建回文。