← 返回题目列表

Codeforces · 1718/D

D. 布伦卡的排列

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

如果数组 $$$a$$$ 中的所有元素都是成对不同的,则我们称该数组为纯数组。例如,数组 $$$[1, 7, 9]$$$ 是纯数组,而 $$$[1, 3, 3, 7]$$$ 则不是,因为 $$$3$$$ 在其中出现了两次。

纯数组 $$$b$$$ 与纯数组 $$$c$$$ 相似,如果它们的长度 $$$n$$$ 相同,并且对于所有索引对 $$$l$$$, $$$r$$$,使得 $$$1 \le l \le r \le n$$$,$$$$$$\operatorname{argmax}([b_l, b_{l + 1}, \ldots, b_r]) = \operatorname{argmax}([c_l, c_{l + 1}, \ldots, c_r]),$$$$$$ 其中 $$$\operatorname{argmax}(x)$$$ 被定义为 $$$x$$$ 中最大元素的索引(对于纯数组来说是唯一的)。例如,$$$\operatorname{argmax}([3, 4, 2]) = 2$$$、$$$\operatorname{argmax}([1337, 179, 57]) = 1$$$。

最近,Tonya 发现 Burenka 非常喜欢长度为 $$$n$$$ 的排列 $$$p$$$。 Tonya 决定取悦她,给她一个类似于 $$$p$$$ 的数组 $$$a$$$。他已经修复了 $$$a$$$ 的一些元素,但恰好缺少 $$$k$$$ 元素(在这些位置暂时 $$$a_i = 0$$$)。保证 $$$k \ge 2$$$。此外,他还有一组 $$$S$$$ 的 $$$k - 1$$$ 号码。

Tonya 意识到他缺少一个号码来填补 $$$a$$$ 的空位,因此他决定购买它。他有 $$$q$$$ 可供购买的期权。 Tonya 认为数字 $$$d$$$ 适合他,如果可以用 $$$S$$$ 中的数字和数字 $$$d$$$ 替换 $$$a$$$ 中的所有零,从而使 $$$a$$$ 成为类似于 $$$p$$$ 的纯数组。对于$$$d$$$的每个选项,输出这个数字是否适合他。

输入

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

每个测试用例的第一行包含几个整数 $$$n$$$ 和 $$$q$$$ ($$$1 \le n, q \le 3 \cdot 10^5$$$)。

每个输入测试用例的第二行包含 $$$n$$$ 整数 $$$p_1, p_2, \ldots, p_n$$$ ($$$1 \le p_i \le n$$$) - Burenka 喜欢的排列。

每个测试用例的第三行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$0 \le a_i \le 10^6$$$) — Tonya 数组的元素,其中 $$$0$$$ 表示缺失元素。保证有两个索引 $$$i, j$$$ $$$(1 \le i, j \le n, i \ne j)$$$ 使得 $$$a_i = 0, a_j = 0$$$,这意味着 $$$k \geq 2$$$。

每个测试用例的第四行包含 $$$k - 1$$$ 不同的整数 $$$s_1, s_2, \ldots, s_{k-1}$$$ ($$$1 \le s_i \le 10^6$$$) — Tonya 集合 $$$S$$$ 的元素。

接下来的 $$$q$$$ 行都包含一个整数 $$$d$$$ ($$$1 \le d \le 10^6$$$) — Tonya 计划购买的数字。

保证对于每个给定的 $$$d$$$ 可以用 $$$S$$$ 中的数字和数字 $$$d$$$ 填充 $$$a$$$ 中的空白以获得纯数组。

保证所有测试中$$$n$$$的总和与$$$q$$$的总和不超过$$$3 \cdot 10^5$$$。

输出

输出 $$$q$$$ 行。对于每个值 $$$d$$$,如果有办法填充数组 $$$a$$$ 使其类似于 $$$p$$$,则打印“YES”,否则打印“NO”。

示例

输入 #1

4
4 3
1 4 3 2
5 0 7 0
6
9
1
4
5 3
1 2 5 4 3
0 5 10 0 0
3 9
1
8
11
5 2
1 4 3 2 5
0 0 0 0 0
7 9 1 5
6
100
4 2
4 1 3 2
0 5 3 0
2
4
6

输出 #1

YES
NO
NO
YES
YES
NO
YES
YES
NO
NO

注意

在第一个测试用例$$$d = 9$$$中,可以得到$$$a = [5, 9, 7, 6]$$$,可以证明$$$a$$$与$$$p$$$类似,对于$$$d=1$$$和$$$d=4$$$可以证明没有答案。

在第二个测试用例中,对于$$$d = 1$$$,可以得到$$$a = [1, 5, 10, 9, 3]$$$,对于$$$d = 8$$$,可以得到$$$a = [3, 5, 10, 9, 8]$$$,可以证明,对于$$$d = 11$$$,不存在回答。