Range Sums

题目描述

Takahashi 有一个秘密的整数序列 $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$ $\hspace{0.4cm}\vdots$ $l_Q$ $r_Q$

输出格式

如果可以确定 $a$ 的所有元素之和，输出 $Yes$；否则，输出 $No$。

3 3
1 2
2 3
2 2

Yes

4 3
1 3
1 2
2 3

No

4 4
1 1
2 2
3 3
1 4

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)$ 输入中的所有数值都是整数。从第一条和第二条信息，我们可以得到值 $a_1+a_2+a_2+a_3$。通过从中减去 $a_2$ 的值，我们可以确定 $a_1+a_2+a_3$。
我们可以确定 $a$ 的前 $3$ 个元素之和，但不能确定所有元素之和。
第四条信息直接给出了所有元素之和。

标签: AtCoder|abc238E

来源

AtCoder|abc238E