← 返回题目列表

Codeforces · 1779/D

D. 鲍里斯和他惊人的发型

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

鲍里斯认为国际象棋是一项乏味的游戏。所以他提前离开了比赛,去了一家理发店,因为他的头发有点乱。

他当前的头发可以用数组 $$$a_1,a_2,\ldots, a_n$$$ 来描述,其中 $$$a_i$$$ 是位置 $$$i$$$ 处头发的高度。他想要的发型可以用数组 $$$b_1,b_2,\ldots, b_n$$$ 以类似的方式描述。

理发师有 $$$m$$$ 剃须刀。每个都有自己的大小,最多可以使用一次。在一次手术中,他选择了一把剃刀,剪掉了鲍里斯的一段头发。更正式地说,操作是:

- 选择任何以前没有使用过的剃须刀,让它的大小为$$$x$$$;
- 选择一个段 $$$[l,r]$$$ ($$$1\leq l \leq r \leq n$$$);
- 设置 $$$a_i := \min (a_i,x)$$$ 为每个 $$$l\leq i \leq r$$$;

请注意,某些剃须刀可能具有相同的尺寸 - 理发师只能选择与尺寸为 $$$x$$$ 的剃须刀数量相同的 $$$x$$$ 尺寸。

他可以执行任意数量的操作,只要任何剃刀最多使用一次,并且最后每个 $$$1 \leq i \leq n$$$ $$$a_i = b_i$$$ 即可。他不必使用所有剃须刀。

你能确定理发师能否给鲍里斯剪出他想要的发型吗?

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \leq t \leq 20\,000$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个正整数 $$$n$$$ ($$$3\leq n\leq 2\cdot 10^5$$$) — 数组 $$$a$$$ 和 $$$b$$$ 的长度。

每个测试用例的第二行包含 $$$n$$$ 正整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — 鲍里斯当前的头发。

每个测试用例的第三行包含 $$$n$$$ 正整数 $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \leq b_i \leq 10^9$$$) — Boris 想要的头发。

每个测试用例的第四行包含一个正整数 $$$m$$$ ($$$1 \leq m \leq 2\cdot 10^5$$$) — 剃须刀的数量。

每个测试用例的第五行包含 $$$m$$$ 正整数 $$$x_1,x_2, \ldots, x_m$$$ ($$$1 \leq x_i \leq 10^9$$$) — 剃须刀的尺寸。

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

输出

对于每个测试用例,如果理发师可以根据需要修剪鲍里斯的头发,请打印“YES”。否则,打印“NO”。

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

示例

输入 #1

7
3
3 3 3
2 1 2
2
1 2
6
3 4 4 6 3 4
3 1 2 3 2 3
3
3 2 3
10
1 2 3 4 5 6 7 8 9 10
1 2 3 4 5 6 7 8 9 10
10
1 2 3 4 5 6 7 8 9 10
3
1 1 1
1 1 2
12
4 2 4 3 1 5 6 3 5 6 2 1
13
7 9 4 5 3 3 3 6 8 10 3 2 5
5 3 1 5 3 2 2 5 8 5 1 1 5
8
1 5 3 5 4 2 3 1
13
7 9 4 5 3 3 3 6 8 10 3 2 5
5 3 1 5 3 2 2 5 8 5 1 1 5
7
1 5 3 4 2 3 1
3
19747843 2736467 938578397
2039844 2039844 2039844
1
2039844

输出 #1

YES
NO
YES
NO
YES
NO
YES

注意

在第一个测试用例中,鲍里斯的头发最初是$$$[3,3,3]$$$。让我们描述理发师可以执行的一系列 $$$2$$$ 操作:

- 理发师在$$$[2,2]$$$段上使用尺寸为$$$1$$$的剃须刀;因此鲍里斯的头发变成$$$[3,1,3]$$$。
- 理发师在$$$[1,3]$$$段上使用尺寸为$$$2$$$的剃须刀;因此鲍里斯的头发变成$$$[2,1,2]$$$,这是所需的发型。

在第三个测试用例中,无需执行任何操作,因为鲍里斯的头发已经达到预期效果。

在第四个测试用例中,任何削减都无法以数组变为 $$$[1,1,2]$$$ 的方式增加 $$$[1,1,1]$$$ 中的第三个元素。