Boris and His Amazing Haircut

题意翻译

给定一个数列 $ a $ 和一个目标数列 $ b $ ，可以进行 $ m $ 种操作，每种操作有一个自己的 $ x $，可以选择任意一段区间 $ [l,r]$，使得 $ \forall i \in[l,r],a_i=\min(a_i,x) $，可能有操作的 $ x $ 是相同的，每种操作只能进行一次，也可以不进行，问能否使得 $ a $ 变成 $ b $。

题目描述

Boris thinks that chess is a tedious game. So he left his tournament early and went to a barber shop as his hair was a bit messy. His current hair can be described by an array $ a_1,a_2,\ldots, a_n $ , where $ a_i $ is the height of the hair standing at position $ i $ . His desired haircut can be described by an array $ b_1,b_2,\ldots, b_n $ in a similar fashion. The barber has $ m $ razors. Each has its own size and can be used at most once. In one operation, he chooses a razor and cuts a segment of Boris's hair. More formally, an operation is: - Choose any razor which hasn't been used before, let its size be $ x $ ; - Choose a segment $ [l,r] $ ( $ 1\leq l \leq r \leq n $ ); - Set $ a_i := \min (a_i,x) $ for each $ l\leq i \leq r $ ; Notice that some razors might have equal sizes — the barber can choose some size $ x $ only as many times as the number of razors with size $ x $ . He may perform as many operations as he wants, as long as any razor is used at most once and $ a_i = b_i $ for each $ 1 \leq i \leq n $ at the end. He does not have to use all razors. Can you determine whether the barber can give Boris his desired haircut?

输入输出格式

输入格式

Each test contains multiple test cases. The first line contains the number of test cases $ t $ ( $ 1 \leq t \leq 20\,000 $ ). The description of the test cases follows. The first line of each test case contains a positive integer $ n $ ( $ 3\leq n\leq 2\cdot 10^5 $ ) — the length of arrays $ a $ and $ b $ . The second line of each test case contains $ n $ positive integers $ a_1, a_2, \ldots, a_n $ ( $ 1 \leq a_i \leq 10^9 $ ) — Boris's current hair. The third line of each test case contains $ n $ positive integers $ b_1, b_2, \ldots, b_n $ ( $ 1 \leq b_i \leq 10^9 $ ) — Boris's desired hair. The fourth line of each test case contains a positive integer $ m $ ( $ 1 \leq m \leq 2\cdot 10^5 $ ) — the number of razors. The fifth line of each test case contains $ m $ positive integers $ x_1,x_2, \ldots, x_m $ ( $ 1 \leq x_i \leq 10^9 $ ) — the sizes of the razors. It is guaranteed that the sum of $ n $ and the sum of $ m $ over all test cases do not exceed $ 2\cdot 10^5 $ .

输出格式

For each test case, print "YES" if the barber can cut Boris's hair as desired. Otherwise, print "NO". You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

输入输出样例

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

说明

In the first test case, Boris's hair is initially $ [3,3,3] $ . Let us describe a sequence of $ 2 $ operations the barber can perform: - The barber uses the razor with size $ 1 $ on the segment $ [2,2] $ ; hence Boris's hair becomes $ [3,1,3] $ . - The barber uses the razor with size $ 2 $ on the segment $ [1,3] $ ; hence Boris's hair becomes $ [2,1,2] $ which is the desired haircut. In the third test case, no operation has to be done since Boris's hair is already as desired. In the fourth test case, no cuts will be able to increase the third element in $ [1,1,1] $ in a way that the array becomes $ [1,1,2] $ .

**鲍里斯和他的惊人发型**

**题意翻译：**
给定一个数列 $ a $ 和一个目标数列 $ b $ ，可以进行 $ m $ 种操作，每种操作有一个自己的 $ x $，可以选择任意一段区间 $ [l,r]$，使得 $ \forall i \in[l,r],a_i=\min(a_i,x) $，可能有操作的 $ x $ 是相同的，每种操作只能进行一次，也可以不进行，问能否使得 $ a $ 变成 $ b $。

**题目描述：**
鲍里斯认为国际象棋是一项无聊的游戏。所以他提前离开了他的比赛，去了理发店，因为他的头发有点乱。

他的当前发型可以用一个数组 $ 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 $）；
- 对于每个 $ l\leq i \leq r $，设置 $ a_i := \min (a_i,x) $；

注意，一些剃刀可能有相同的大小——理发师可以选择某个大小 $ x $ 的次数等于大小为 $ x $ 的剃刀数量。

他可以进行任意多次操作，只要任何剃刀最多使用一次，并且最终 $ a_i = b_i $ 对于每个 $ 1 \leq i \leq n $。他不必使用所有的剃刀。

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

**输入输出格式：**

**输入格式：**
每个测试包含多个测试用例。第一行包含测试用例的数量 $ 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 $）——鲍里斯想要的头发。

每个测试用例的第四行包含一个正整数 $ 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 **鲍里斯和他的惊人发型** **题意翻译：** 给定一个数列 $ a $ 和一个目标数列 $ b $ ，可以进行 $ m $ 种操作，每种操作有一个自己的 $ x $，可以选择任意一段区间 $ [l,r]$，使得 $ \forall i \in[l,r],a_i=\min(a_i,x) $，可能有操作的 $ x $ 是相同的，每种操作只能进行一次，也可以不进行，问能否使得 $ a $ 变成 $ b $。 **题目描述：** 鲍里斯认为国际象棋是一项无聊的游戏。所以他提前离开了他的比赛，去了理发店，因为他的头发有点乱。 他的当前发型可以用一个数组 $ 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 $）； - 对于每个 $ l\leq i \leq r $，设置 $ a_i := \min (a_i,x) $； 注意，一些剃刀可能有相同的大小——理发师可以选择某个大小 $ x $ 的次数等于大小为 $ x $ 的剃刀数量。 他可以进行任意多次操作，只要任何剃刀最多使用一次，并且最终 $ a_i = b_i $ 对于每个 $ 1 \leq i \leq n $。他不必使用所有的剃刀。 你能确定理发师能否给鲍里斯理出他想要的发型吗？ **输入输出格式：** **输入格式：** 每个测试包含多个测试用例。第一行包含测试用例的数量 $ 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 $）——鲍里斯想要的头发。 每个测试用例的第四行包含一个正整数 $ 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