← 返回题目列表

AtCoder · abc238_e

H. 范围总和

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

分数: 500 点

问题陈述

高桥有一个秘密整数序列 a。你知道的长度 a is N.

你想猜的内容 a。他已承诺给你以下 Q 附加信息。

  • 的 树的 i第信息:值 a_{l_i}+a_{l_i+1}+\cdots+a_{r_i}.

是否可以确定中所有元素的总和 a, a_1+a_2+\cdots+a_N,如果 Q 承诺的信息是否给出?

约束

  • 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

我们可以确定第一个的总和 3 的元素 a,但不是所有元素的总和。


示例输入 3

4 4
1 1
2 2
3 3
1 4

示例输出 3

Yes

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