Sanae and Giant Robot

题意翻译

> 果然是那个吗！因为其实用性而无法被实现的！只能出现于憧憬中的，二足步行巨大机器人！——东风谷早苗，《东方非想天则》 早苗制造了一台巨大的机器人——非想天则，但是这个机器人出了一些故障。更糟糕的是，早苗不知道如何将其停止运行，因而早苗只能在机器人运行的时候对其修复。 非想天则的状态可以用一个正整数数列 $n$ 来表示。非想天则现在处于状态 $a_1,a_2,\dots a_n$，而早苗希望将其变为 $b_1,b_2,\dots,b_n$。 作为一位优秀的女子高中生，早苗非常了解复制粘贴的艺术。她有 $m$ 个可供选择的区间，在每一次操作中，早苗可以把序列 $b$ 中的一个可选择的区间对应位置地复制粘贴到序列 $a$ 中，前提是要求序列 $a$ 的每个数字的总和不变。形式化地来讲，早苗可以选择一个区间 $[l,r]$，执行操作 $a_i \leftarrow b_i (l \leq i \leq r)$，当且仅当 $\sum \limits_{i=1}^n a_i$ 不变。 请你判断早苗能否通过若干次这样的操作，将非想天则的状态由序列 $a$ 转化为序列 $b$。 **输入格式** 第一行输入一个正整数 $t(1 \leq t \leq 2 \times 10^4)$，表示输入数据组数。 对于每组数据，首先输入两个正整数 $n,m(2 \leq n \leq 2 \times 10^5,1 \leq m \leq 10^5)$，分别表示数列 $a,b$ 的长度和可以操作的区间个数。 第二行输入 $n$ 个正整数 $a_i(1 \leq a_i \leq 10^9)$，表示非想天则的状态。 第三行输入 $n$ 个正整数 $b_i(1 \leq b_i \leq 10^9)$，表示早苗希望非想天则变成的状态。 接下来输入 $m$ 行，每行两个正整数 $l,r(1 \leq l < r \leq n)$，表示早苗可以进行操作的区间。 数据保证，$\sum n,\sum m \leq 2 \times 10^5$。 **输出格式** 如果早苗可以将数列 $a$ 转化为数列 $b$，则输出 `YES`，否则输出 `NO`，不区分大小写。

题目描述

Is it really?! The robot only existing in my imagination?! The Colossal Walking Robot?!! — Kochiya Sanae Sanae made a giant robot — Hisoutensoku, but something is wrong with it. To make matters worse, Sanae can not figure out how to stop it, and she is forced to fix it on-the-fly.The state of a robot can be represented by an array of integers of length $ n $ . Initially, the robot is at state $ a $ . She wishes to turn it into state $ b $ . As a great programmer, Sanae knows the art of copy-and-paste. In one operation, she can choose some segment from given segments, copy the segment from $ b $ and paste it into the same place of the robot, replacing the original state there. However, she has to ensure that the sum of $ a $ does not change after each copy operation in case the robot go haywire. Formally, Sanae can choose segment $ [l,r] $ and assign $ a_i = b_i $ ( $ l\le i\le r $ ) if $ \sum\limits_{i=1}^n a_i $ does not change after the operation. Determine whether it is possible for Sanae to successfully turn the robot from the initial state $ a $ to the desired state $ b $ with any (possibly, zero) operations.

输入输出格式

输入格式

Each test contains multiple test cases. The first line contains a single integer $ t $ ( $ 1 \leq t \leq 2\cdot 10^4 $ ) — the number of test cases. The descriptions of the test cases follow. The first line of each test case contains two integers $ n $ , $ m $ ( $ 2 \leq n\leq 2\cdot 10^5 $ , $ 1 \leq m\leq 2\cdot 10^5 $ ) — the length of $ a $ , $ b $ and the number of segments. The second line contains $ n $ intergers $ a_1,a_2,\ldots,a_n $ ( $ 1 \leq a_i \leq 10^9 $ ) — the initial state $ a $ . The third line contains $ n $ intergers $ b_1,b_2,\ldots,b_n $ ( $ 1 \leq b_i \leq 10^9 $ ) — the desired state $ b $ . Then $ m $ lines follow, the $ i $ -th line contains two intergers $ l_i,r_i $ ( $ 1 \leq l_i < r_i \leq n $ ) — the segments that can be copy-pasted by Sanae. It is guaranteed that both the sum of $ n $ and the sum of $ m $ over all test cases does not exceed $ 2 \cdot 10 ^ 5 $ .

输出格式

For each test case, print "YES" (without quotes) if $ a $ can be turned into $ b $ , or "NO" (without quotes) otherwise. You can output "YES" and "NO" in any case (for example, strings "yEs", "yes" and "Yes" will be recognized as a positive response).

输入输出样例

输入样例 #1

2
5 2
1 5 4 2 3
3 2 5 4 1
1 3
2 5
5 2
1 5 4 2 3
3 2 4 5 1
1 2
2 4

输出样例 #1

YES
NO

说明

Test case 1: One possible way of turning $ a $ to $ b $ : First, select $ [1,3] $ . After the operation, $ a=[3,2,5,2,3] $ . Then, select $ [2,5] $ . After the operation, $ a=[3,2,5,4,1]=b $ . Test case 2: It can be shown that it is impossible to turn $ a $ into $ b $ .

**题目大意**：

东风谷早苗制造了一个巨大的机器人——非想天则，但是机器人出现了一些故障。更糟糕的是，早苗不知道如何将其停止运行，因此只能在机器人运行的时候对其修复。非想天则的状态可以用一个正整数数列 $ n $ 来表示。非想天则现在处于状态 $ a_1,a_2,\dots a_n $，而早苗希望将其变为 $ b_1,b_2,\dots,b_n $。

早苗有 $ m $ 个可供选择的区间，在每一次操作中，早苗可以把序列 $ b $ 中的一个可选择的区间对应位置地复制粘贴到序列 $ a $ 中，前提是要求序列 $ a $ 的每个数字的总和不变。形式化地来讲，早苗可以选择一个区间 $[l,r]$，执行操作 $ a_i \leftarrow b_i $ ( $ l \leq i \leq r $ )，当且仅当 $ \sum \limits_{i=1}^n a_i $ 不变。

请你判断早苗能否通过若干次这样的操作，将非想天则的状态由序列 $ a $ 转化为序列 $ b $。

**输入格式**：

第一行输入一个正整数 $ t(1 \leq t \leq 2 \times 10^4) $，表示输入数据组数。
对于每组数据，首先输入两个正整数 $ n,m(2 \leq n \leq 2 \times 10^5,1 \leq m \leq 10^5) $，分别表示数列 $ a,b $ 的长度和可以操作的区间个数。
第二行输入 $ n $ 个正整数 $ a_i(1 \leq a_i \leq 10^9) $，表示非想天则的状态。
第三行输入 $ n $ 个正整数 $ b_i(1 \leq b_i \leq 10^9) $，表示早苗希望非想天则变成的状态。
接下来输入 $ m $ 行，每行两个正整数 $ l,r(1 \leq l < r \leq n) $，表示早苗可以进行操作的区间。
数据保证，$ \sum n,\sum m \leq 2 \times 10^5 $。

**输出格式**：

如果早苗可以将数列 $ a $ 转化为数列 $ b $，则输出 `YES`，否则输出 `NO`，不区分大小写。**题目大意**： 东风谷早苗制造了一个巨大的机器人——非想天则，但是机器人出现了一些故障。更糟糕的是，早苗不知道如何将其停止运行，因此只能在机器人运行的时候对其修复。非想天则的状态可以用一个正整数数列 $ n $ 来表示。非想天则现在处于状态 $ a_1,a_2,\dots a_n $，而早苗希望将其变为 $ b_1,b_2,\dots,b_n $。 早苗有 $ m $ 个可供选择的区间，在每一次操作中，早苗可以把序列 $ b $ 中的一个可选择的区间对应位置地复制粘贴到序列 $ a $ 中，前提是要求序列 $ a $ 的每个数字的总和不变。形式化地来讲，早苗可以选择一个区间 $[l,r]$，执行操作 $ a_i \leftarrow b_i $ ( $ l \leq i \leq r $ )，当且仅当 $ \sum \limits_{i=1}^n a_i $ 不变。 请你判断早苗能否通过若干次这样的操作，将非想天则的状态由序列 $ a $ 转化为序列 $ b $。 **输入格式**： 第一行输入一个正整数 $ t(1 \leq t \leq 2 \times 10^4) $，表示输入数据组数。 对于每组数据，首先输入两个正整数 $ n,m(2 \leq n \leq 2 \times 10^5,1 \leq m \leq 10^5) $，分别表示数列 $ a,b $ 的长度和可以操作的区间个数。 第二行输入 $ n $ 个正整数 $ a_i(1 \leq a_i \leq 10^9) $，表示非想天则的状态。 第三行输入 $ n $ 个正整数 $ b_i(1 \leq b_i \leq 10^9) $，表示早苗希望非想天则变成的状态。 接下来输入 $ m $ 行，每行两个正整数 $ l,r(1 \leq l < r \leq n) $，表示早苗可以进行操作的区间。 数据保证，$ \sum n,\sum m \leq 2 \times 10^5 $。 **输出格式**： 如果早苗可以将数列 $ a $ 转化为数列 $ b $，则输出 `YES`，否则输出 `NO`，不区分大小写。