← 返回题目列表

Codeforces · 1980/C

C. 索菲亚和丢失的行动

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

Sofia 有一个 $$$n$$$ 整数数组 $$$a_1, a_2, \ldots, a_n$$$。有一天,她厌倦了它,所以她决定依次对其应用 $$$m$$$ 修改操作。

每个修改操作由一对数字 $$$\langle c_j, d_j \rangle$$$ 描述,表示索引为 $$$c_j$$$ 的数组元素应赋值为 $$$d_j$$$,即执行赋值 $$$a_{c_j} = d_j$$$。按顺序应用所有修改操作后,Sofia 丢弃了生成的数组。

最近,您发现了一个由 $$$n$$$ 整数 $$$b_1, b_2, \ldots, b_n$$$ 组成的数组。您感兴趣的是这个数组是否是 Sofia 的数组。您知道原始数组的值,以及值 $$$d_1、d_2、\ldots、d_m$$$。结果 $$$c_1、c_2、\ldots、c_m$$$ 值丢失了。

是否存在一个序列 $$$c_1, c_2, \ldots, c_m$$$ 使得修改操作 $$$\langle c_1, d_1, \rangle, \langle c_2, d_2, \rangle, \ldots, \langle c_m, d_m \rangle$$$ 顺序应用到数组 $$$a_1, a_2, \ldots, a_n$$$ 将其转换为数组$$$b_1, b_2, \ldots, b_n$$$?

输入

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

然后按照测试用例的描述进行操作。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$1 \le n \le 2 \cdot 10^5$$$) — 数组的大小。

每个测试用例的第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) - 原始数组的元素。

每个测试用例的第三行包含 $$$n$$$ 整数 $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le 10^9$$$) — 找到的数组的元素。

第四行包含一个整数 $$$m$$$ ($$$1 \le m \le 2 \cdot 10^5$$$) — 修改操作的数量。

第五行包含 $$$m$$$ 整数 $$$d_1, d_2, \ldots, d_m$$$ ($$$1 \le d_j \le 10^9$$$) - 每个修改操作的保留值。

保证所有测试用例的$$$n$$$值之和不超过$$$2 \cdot 10^5$$$,同样所有测试用例的$$$m$$$值之和不超过$$$2 \cdot 10^5$$$。

输出

输出$$$t$$$行,每一行都是对应测试用例的答案。作为答案,如果存在合适的序列 $$$c_1, c_2, \ldots, c_m$$$,则输出“YES”,否则输出“NO”。

您可以在任何情况下输出答案(例如,字符串“yEs”、“yes”、“Yes”和“YES”将被识别为肯定答案)。

示例

输入 #1

7
3
1 2 1
1 3 2
4
1 3 1 2
4
1 2 3 5
2 1 3 5
2
2 3
5
7 6 1 10 10
3 6 1 11 11
3
4 3 11
4
3 1 7 8
2 2 7 10
5
10 3 2 2 1
5
5 7 1 7 9
4 10 1 2 9
8
1 1 9 8 7 2 10 4
4
1000000000 203 203 203
203 1000000000 203 1000000000
2
203 1000000000
1
1
1
5
1 3 4 5 1

输出 #1

YES
NO
NO
NO
YES
NO
YES