AT_abc238_e [ABC238E] Range Sums

题目描述

高桥君有一个秘密的整数序列 $a$，目前你只知道 $a$ 的长度为 $N$。

你想要猜出 $a$ 的内容，高桥君承诺会额外给你 $Q$ 条如下信息：

• 第 $i$ 条信息：$a_{l_i}+a_{l_i+1}+\cdots+a_{r_i}$ 的值。

如果高桥君信守承诺，给出了全部 $Q$ 条信息，你能否确定 $a$ 中所有元素的总和 $a_1+a_2+\cdots+a_N$ 的值？

输入格式

输入以如下格式从标准输入给出。

$N$ $Q$
$l_1$ $r_1$
$l_2$ $r_2$
$\vdots$
$l_Q$ $r_Q$

输出格式

如果能够确定 $a$ 中所有元素的总和，则输出 Yes，否则输出 No。

输入输出样例 #1

输入 #1

3 3
1 2
2 3
2 2

输出 #1

Yes

输入输出样例 #2

输入 #2

4 3
1 3
1 2
2 3

输出 #2

No

输入输出样例 #3

输入 #3

4 4
1 1
2 2
3 3
1 4

输出 #3

Yes

说明/提示

约束条件

• $1 \leq N \leq 2 \times 10^5$
• $1 \leq Q \leq \min(2 \times 10^5, \frac{N(N+1)}{2})$
• $1 \leq l_i \leq r_i \leq N$
• $(l_i, r_i) \neq (l_j, r_j)\ (i \neq j)$
• 所有输入均为整数。

样例解释 1

通过第 $1$ 条和第 $2$ 条信息，可以知道 $a_1+a_2+a_2+a_3$ 的值。再用第 $3$ 条信息得到的 $a_2$ 的值相减，就可以确定 $a_1+a_2+a_3$ 的值。

样例解释 2

可以确定 $a$ 的前 $3$ 项的总和，但无法确定所有元素的总和。

样例解释 3

第 $4$ 条信息直接给出了所有元素的总和。

由 ChatGPT 4.1 翻译