分数: 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
第四个信息直接给出了所有元素的总和。