← 返回题目列表

Codeforces · 1687/C

C. 早苗和巨型机器人

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

机器人的状态可以用长度为 $$$n$$$ 的整数数组表示。最初,机器人处于状态$$$a$$$。她希望将其变成状态$$$b$$$。

作为一名出色的程序员,早苗深谙复制粘贴的艺术。在一次操作中,她可以从给定的段中选择一些段,从 $$$b$$$ 复制该段并将其粘贴到机器人的同一位置,替换那里的原始状态。然而,她必须确保每次复制操作后 $$$a$$$ 的总和不会改变,以防机器人失控。形式上,如果$$$\sum\limits_{i=1}^n a_i$$$在操作后没有改变,早苗可以选择段$$$[l,r]$$$并分配$$$a_i = b_i$$$ ($$$l\le i\le r$$$)。

确定 Sanae 是否可以通过任何(可能是零)操作成功地将机器人从初始状态 $$$a$$$ 转到所需状态 $$$b$$$。

输入

每个测试包含多个测试用例。第一行包含一个整数 $$$t$$$ ($$$1 \leq t \leq 2\cdot 10^4$$$) — 测试用例的数量。测试用例的描述如下。

每个测试用例的第一行包含两个整数 $$$n$$$、$$$m$$$ ($$$2 \leq n\leq 2\cdot 10^5$$$, $$$1 \leq m\leq 2\cdot 10^5$$$) — $$$a$$$、$$$b$$$ 的长度和段数。

第二行包含 $$$n$$$ 整数 $$$a_1,a_2,\ldots,a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — 初始状态 $$$a$$$。

第三行包含 $$$n$$$ 整数 $$$b_1,b_2,\ldots,b_n$$$ ($$$1 \leq b_i \leq 10^9$$$) — 所需状态 $$$b$$$。

接下来是 $$$m$$$ 行,第 $$$i$$$ 行包含两个整数 $$$l_i,r_i$$$ ($$$1 \leq l_i < r_i \leq n$$$) — 可以由 Sanae 复制粘贴的段。

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

输出

对于每个测试用例,如果 $$$a$$$ 可以转换为 $$$b$$$,则打印“YES”(不带引号),否则打印“NO”(不带引号)。

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

示例

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

注意

测试用例1:

将 $$$a$$$ 转换为 $$$b$$$ 的一种可能方法:

首先,选择$$$[1,3]$$$。运算后$$$a=[3,2,5,2,3]$$$。

然后,选择$$$[2,5]$$$。运算后$$$a=[3,2,5,4,1]=b$$$。

测试用例2:

可以证明$$$a$$$ 不可能变成$$$b$$$。