A15112. Sanae and Giant Robot
编程题
普及/提高-
知识点
题目描述
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.
— 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$ .
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).
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$ .
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$ .