Permutation for Burenka

题意翻译

### 题目描述 如果一个数组里面任意两个数字都是不同的，我们把这种数组称作为一个“纯数组”。举个例子。$[1,7,9]$ 是纯数组，$[1,3,3,7]$ 不是，因为 $3$ 出现了两次。 如果两个纯数组 $b,c$ 的长度相等且“类似”，并且对于所有数组中的 $l$ 和 $r (l \leq l \leq r \leq n)$，都满足 $\text{argmax}([b_l,b_{l+1}, \ldots, b_r])= \text{argmax}([c_l,c_{l+1}, \ldots, c_r]).$ $\text{argmax(x)}$ 返回值是 $x$ 中最大值的下标。举个例子，$\text{argmax}([1337,179,57])=1.$ 最近，Tonya 发现 Burenka 非常喜欢长度为 $n$ 的排列 $p$。 Tonya 为了让她开心，于是给她一个类似于 $p$ 的数组。他已经修复了 $a$ 的一些元素，但恰好缺少 $k$ 个元素（在这些位置 $a_i$ 暂时等于 $0$）。保证$k≥2$。此外，他有一个由 $k-1$ 个数字组成的集合 $S$。 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`。 #### 提示 ## 提示 在 $ 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 $ 没有答案。

题目描述

We call an array $ a $ pure if all elements in it are pairwise distinct. For example, an array $ [1, 7, 9] $ is pure, $ [1, 3, 3, 7] $ isn't, because $ 3 $ occurs twice in it. A pure array $ b $ is similar to a pure array $ c $ if their lengths $ n $ are the same and for all pairs of indices $ l $ , $ r $ , such that $ 1 \le l \le r \le n $ , it's true that $ $\operatorname{argmax}([b_l, b_{l + 1}, \ldots, b_r]) = \operatorname{argmax}([c_l, c_{l + 1}, \ldots, c_r]), $ $ where $ \\operatorname{argmax}(x) $ is defined as the index of the largest element in $ x $ (which is unique for pure arrays). For example, $ \\operatorname{argmax}(\[3, 4, 2\]) = 2 $ , $ \\operatorname{argmax}(\[1337, 179, 57\]) = 1 $ .</p><p>Recently, Tonya found out that Burenka really likes a permutation $ p $ of length $ n $ . Tonya decided to please her and give her an array $ a $ <span class="tex-font-style-it">similar</span> to $ p $ . He already fixed some elements of $ a $ , but exactly $ k $ elements are missing (in these positions temporarily $ a\_i = 0 $ ). It is guaranteed that $ k \\ge 2 $ . Also, he has a set $ S $ of $ k - 1 $ numbers.</p><p>Tonya realized that he was missing one number to fill the empty places of $ a $ , so he decided to buy it. He has $ q $ options to buy. Tonya thinks that the number $ d $ suits him, if it is possible to replace all zeros in $ a $ with numbers from $ S $ and the number $ d $ , so that $ a $ becomes a <span class="tex-font-style-it">pure</span> array <span class="tex-font-style-it">similar</span> to $ p $ . For each option of $ d$, output whether this number is suitable for him or not.

输入输出格式

输入格式

The first line contains a single integer $ t $ ( $ 1 \le t \le 10^4 $ ) is the number of test cases. The description of the test cases follows. The first line of each test case contains a couple of integers $ n $ and $ q $ ( $ 1 \le n, q \le 3 \cdot 10^5 $ ). The second line of each input test case contains $ n $ integers $ p_1, p_2, \ldots, p_n $ ( $ 1 \le p_i \le n $ ) — the permutation Burenka likes. The third line of each test case contains $ n $ integers $ a_1, a_2, \ldots, a_n $ ( $ 0 \le a_i \le 10^6 $ ) — elements of Tonya's array, where $ 0 $ denotes a missing element. It is guaranteed that there are two indexes $ i, j $ $ (1 \le i, j \le n, i \ne j) $ such that $ a_i = 0, a_j = 0 $ , which implies that $ k \geq 2 $ . The fourth line of each test case contains $ k - 1 $ distinct integers $ s_1, s_2, \ldots, s_{k-1} $ ( $ 1 \le s_i \le 10^6 $ ) — elements of Tonya's set $ S $ . Each of the next $ q $ lines contains a single integer $ d $ ( $ 1 \le d \le 10^6 $ ) — the number that Tonya plans to buy. It is guaranteed that for each given $ d $ it's possible to fill in the gaps in $ a $ with numbers from $ S $ and the number $ d $ to get a pure array. It is guaranteed that the sum of $ n $ and the sum of $ q $ in all tests does not exceed $ 3 \cdot 10^5 $ .

输出格式

Output $ q $ lines. For each value $ d $ , print "YES" if there is a way to fill the array $ a $ to make it similar to $ p $ , and "NO" otherwise.

输入输出样例

输入样例 #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

说明

In the first test case for $ d = 9 $ , you can get $ a = [5, 9, 7, 6] $ , it can be proved that $ a $ is similar to $ p $ , for $ d=1 $ and $ d=4 $ it can be proved that there is no answer. In the second test case for $ d = 1 $ , you can get $ a = [1, 5, 10, 9, 3] $ , for $ d = 8 $ , you can get $ a = [3, 5, 10, 9, 8] $ , it can be proved that for $ d = 11 $ there is no answer.

**题目大意**：

定义一个数组如果没有重复的元素，那么这个数组是“纯数组”。例如，数组 $[1,7,9]$ 是纯数组，而 $[1,3,3,7]$ 不是，因为数字 $3$ 出现了两次。

如果两个纯数组的长度相同，并且在任意区间内最大值的下标相同，那么这两个数组是“类似”的。例如，对于数组 $[1337,179,57]$，$\text{argmax}$ 的结果是 $1$。

Tonya 发现 Burenka 喜欢长度为 $n$ 的排列 $p$。Tonya 为了让她开心，给了她一个类似于 $p$ 的数组 $a$。他已经修复了 $a$ 的一些元素，但还有 $k$ 个元素缺失（在这些位置上 $a_i$ 暂时等于 $0$），保证 $k \geq 2$。此外，他有一个由 $k-1$ 个数字组成的集合 $S$。

Tonya 意识到他缺少一个数字来填补 $a$ 的空白，所以他决定买下它。他有 $q$ 个购买的选择。对于每个选项 $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 计划购买的数字。

**输出格式**：
- 输出 $q$ 行。对于每个值 $d$，如果有办法填充数组 $a$ 来使其类似于 $p$，则输出 `YES`，否则输出 `NO`。**题目大意**： 定义一个数组如果没有重复的元素，那么这个数组是“纯数组”。例如，数组 $[1,7,9]$ 是纯数组，而 $[1,3,3,7]$ 不是，因为数字 $3$ 出现了两次。 如果两个纯数组的长度相同，并且在任意区间内最大值的下标相同，那么这两个数组是“类似”的。例如，对于数组 $[1337,179,57]$，$\text{argmax}$ 的结果是 $1$。 Tonya 发现 Burenka 喜欢长度为 $n$ 的排列 $p$。Tonya 为了让她开心，给了她一个类似于 $p$ 的数组 $a$。他已经修复了 $a$ 的一些元素，但还有 $k$ 个元素缺失（在这些位置上 $a_i$ 暂时等于 $0$），保证 $k \geq 2$。此外，他有一个由 $k-1$ 个数字组成的集合 $S$。 Tonya 意识到他缺少一个数字来填补 $a$ 的空白，所以他决定买下它。他有 $q$ 个购买的选择。对于每个选项 $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 计划购买的数字。 **输出格式**： - 输出 $q$ 行。对于每个值 $d$，如果有办法填充数组 $a$ 来使其类似于 $p$，则输出 `YES`，否则输出 `NO`。