← 返回题目列表

Codeforces · 2211/C1

C1. 等多重组(简单版)

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

这是问题的简单版本。版本之间的差异在于,在此版本中,数组 $$$a$$$ 保证是一个排列。只有解决了该问题的所有版本,您才能破解。

给定一个大小为 $$$n$$$ 的数组 $$$a$$$ 和一个参数 $$$k$$$,调用一个数组 $$$b$$$ 酷 如果满足以下条件:

  • 对于从 $$$k$$$ 到 $$$n$$$ 的每个 $$$i$$$,数组 $$$[a_{i-k+1},a_{i-k+2},\ldots,a_i]$$$ 是以下内容的重新排列$$$[b_{i-k+1},b_{i-k+2},\ldots,b_i]$$$。

给定两个数组 $$$a$$$ 和 $$$b$$$,大小为 $$$n$$$,以及一个整数 $$$k$$$。数组$$$a$$$ 保证是一个排列$$$^{\text{*}}$$$。数组$$$b$$$仅包含从$$$1$$$到$$$n$$$和$$$-1$$$的整数。

确定是否可以将 $$$b$$$ 中的所有 $$$-1$$$ 替换为从 $$$1$$$ 到 $$$n$$$ 的整数,使得 $$$b$$$ 为 酷 关于$$$k$$$。

$$$^{\text{*}}$$$长度$$$n$$$的排列是一个由从$$$1$$$到$$$n$$$以任意顺序的$$$n$$$个不同整数组成的数组。例如,$$$[2,3,1,5,4]$$$是一个排列,但$$$[1,2,2]$$$不是排列($$$2$$$在数组中出现两次),$$$[1,3,4]$$$也不是排列($$$n=3$$$但数组中有$$$4$$$)。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$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 \le a_i \le n$$$)。 在此版本中,保证从 $$$1$$$ 到 $$$n$$$ 的每个数字恰好出现一次。

每个测试用例的第三行包含 $$$n$$$ 整数 $$$b_1,b_2,\ldots,b_n$$$ ($$$1 \leq b_i \leq n$$$ 或 $$$b_i=-1$$$)。

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

输出

对于每个测试用例,输出 是 如果可能的话,并且 NO 否则。您可以用大写或小写打印每个字母。

示例

输入
复制

4
5 5
1 2 3 4 5
3 1 5 2 4
5 4
4 1 2 5 3
2 -1 -1 -1 -1
6 4
1 2 4 3 5 6
-1 -1 3 -1 -1 -1
6 4
1 2 4 3 5 6
-1 -1 3 3 -1 -1

输出
复制

YES
NO
YES
NO

注意

在第一个测试用例中,我们有 $$$k=5$$$。唯一大小为 $$$5$$$ 的子数组是 $$$[1,5]$$$。我们可以看到$$$b$$$是$$$a$$$的重新排列,所以答案是 是.

在第二个测试用例中,可以证明不可能替换$$$b$$$中的所有$$$-1$$$,使得每个大小为$$$k=4$$$的子数组都是彼此的重新排列。