CF2211C2 Equal Multisets (Hard Version)

这是该问题的难版本。不同之处在于本版本中数组 $a$ 是任意的。只有在你解决了所有版本的题目后，才能进行 Hack。 给定一个大小为 $n$ 的数组 $a$ 和参数 $k$，如果数组 $b$ 满足以下条件，则称 $b$ 是 cool 的： - 对于每个 $i$，其中 $k \leq i \leq n$，数组 $[a_{i-k+1}, a_{i-k+2},\ldots,a_i]$ 是 $[b_{i-k+1},b_{i-k+2},\ldots,b_i]$ 的一个重排列。 你会得到两个大小为 $n$ 的数组 $a$ 和 $b$，以及一个整数 $k$。数组 $a$ 仅包含 $1$ 到 $n$ 之间的整数。数组 $b$ 仅包含 $1$ 到 $n$ 之间的整数以及 $-1$。 请判断是否可以将 $b$ 中所有的 $-1$ 替换为 $1$ 到 $n$ 之间的整数，使得 $b$ 关于 $k$ 是 cool 的。

每组测试数据包含多组测试用例。第一行为测试用例组数 $t$（$1 \leq t \leq 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$）。 第三行为 $n$ 个整数 $b_1,b_2,\ldots,b_n$（$1 \leq b_i \leq n$ 或 $b_i=-1$）。 保证所有测试用例的 $n$ 之和不超过 $2 \cdot 10^5$。

对于每个测试用例，如果存在可能方案，请输出 YES，否则输出 NO。你可以用大写或小写字母输出。

在第一个测试用例中，$k=5$。唯一一个大小为 $5$ 的子数组为 $[1,5]$。可以看到 $b$ 是 $a$ 的一个重排列，所以答案是 YES。 在第二个测试用例中，可以令 $b=[2,1,2,1,2]$。可以看到 $a$ 和 $b$ 中任意长度为 $2$ 的窗口都是 $[1,2]$ 或 $[2,1]$，互为重排列，所以答案是 YES。 在第四个测试用例中，$a_1 \neq b_1$ 且 $k=1$，所以答案是 NO。 由 ChatGPT 5 翻译