102384: [AtCoder]ABC238 E - Range Sums

Problem Statement

Takahashi has a secret integer sequence $a$. You know that the length of $a$ is $N$.

You want to guess the contents of $a$. He has promised to give you the following $Q$ additional pieces of information.

• The $i$-th information: the value $a_{l_i}+a_{l_i+1}+\cdots+a_{r_i}$.

Is it possible to determine the sum of all elements in $a$, $a_1+a_2+\cdots+a_N$, if the $Q$ pieces of promised information are given?

Constraints

• $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)$
• All values in input are integers.

Input

Input is given from Standard Input in the following format:

$N$ $Q$
$l_1$ $r_1$
$l_2$ $r_2$
$\hspace{0.4cm}\vdots$
$l_Q$ $r_Q$

Output

If it is possible to determine the sum of all elements in $a$, print Yes; otherwise, print No.

Sample Input 1

3 3
1 2
2 3
2 2

Sample Output 1

Yes

From the first and second information, we can find the value $a_1+a_2+a_2+a_3$. By subtracting the value of $a_2$ from it, we can determine the value $a_1+a_2+a_3$.

Sample Input 2

4 3
1 3
1 2
2 3

Sample Output 2

No

We can determine the sum of the first $3$ elements of $a$, but not the sum of all elements.

Sample Input 3

4 4
1 1
2 2
3 3
1 4

Sample Output 3

Yes

The fourth information directly gives us the sum of all elements.

问题描述

高桥有一个秘密的整数序列$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$？

约束

• $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)$
• 输入中的所有值都是整数。

输入

输入从标准输入以以下格式给出：

$N$ $Q$
$l_1$ $r_1$
$l_2$ $r_2$
$\hspace{0.4cm}\vdots$
$l_Q$ $r_Q$

输出

如果可以确定$a$中所有元素的和，打印Yes；否则，打印No。

样例输入1

3 3
1 2
2 3
2 2

样例输出1

Yes

从第一条和第二条信息，我们可以找到$a_1+a_2+a_2+a_3$的值。从中减去$a_2$的值，我们可以确定$a_1+a_2+a_3$的值。

样例输入2

4 3
1 3
1 2
2 3

样例输出2

No

我们可以确定$a$中前$3$个元素的和，但不能确定所有元素的和。

样例输入3

4 4
1 1
2 2
3 3
1 4

样例输出3

Yes

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