#M. Range Sums

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z [ \ ] ^ _ ` a b c d e f g h i j k l
    Type: RemoteJudge 2000ms 256MiB

Range Sums

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题面翻译

输入一个 nn 和 qq 分别表示数组长度为 nn，有 qq 次输入：

每次输入一个 ll 和 rr，表示我们知道 ll 到 rr 区间的和

问你最后能否知道数组的和

如果可以输出 Yes ，否则输出 No 。

题目描述

高橋くんは秘密の整数列 a a を持っており、現時点で、a a の長さが N N であることは分かっています。

a a の中身を当てたいあなたに対し、高橋くんは以下の Q Q 個の情報を追加で与えてくれることを約束しました。

  • i (1 ≤ i ≤ Q) i\ (1\ \leq\ i\ \leq\ Q) 個目の情報: ali+ali+1+⋯+ari a_{l_i}+a_{l_i+1}+\cdots+a_{r_i} の値

高橋くんが約束を守り、Q Q 個の情報すべてが与えられた場合、a a に含まれる全要素の総和 a1+a2+⋯+aN a_1+a_2+\cdots+a_N を特定することは可能ですか？

输入格式

入力は以下の形式で標準入力から与えられる。

N N Q Q l1 l_1 r1 r_1 l2 l_2 r2 r_2 ⋮ \hspace{0.4cm}\vdots lQ l_Q rQ r_Q

输出格式

a 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 ≤ N ≤ 2 × 105 1\ \leq\ N\ \leq\ 2\ \times\ 10^5
  • 1 ≤ Q ≤ min⁡(2 × 105,N(N+1)2) 1\ \leq\ Q\ \leq\ \min(2\ \times\ 10^5,\frac{N(N+1)}{2})
  • 1 ≤ li ≤ ri ≤ N 1\ \leq\ l_i\ \leq\ r_i\ \leq\ N
  • (li,ri) ≠ (lj,rj) (i ≠ j) (l_i,r_i)\ \neq\ (l_j,r_j)\ (i\ \neq\ j)
  • 入力はすべて整数

Sample Explanation 1

1 1 個目の情報と 2 2 個目の情報から、a1+a2+a2+a3 a_1+a_2+a_2+a_3 の値が分かります。そこから 3 3 個目の情報によって得られる a2 a_2 の値を引くと、a1+a2+a3 a_1+a_2+a_3 の値を特定可能です。

Sample Explanation 2

a a の先頭 3 3 項の総和を特定することは可能ですが、全要素の総和を特定することは不可能です。

Sample Explanation 3

4 4 個目の情報によって全要素の総和が直接与えられています。

北辰OI提高组第2周序列问题课后练习题👍

Not Attended
Status
Done
Rule
IOI
Problem
44
Start at
2024-1-7 16:00
End at
2024-2-18 8:00
Duration
1000 hour(s)
Host
Partic.
15
  1. About
  2. Contact Us
  3. Privacy
  4. Terms of Service
  5. Copyright Complaint
  6. Language
  7. Legacy mode
  8. Theme
  2. text

  4. 鲁公网安备 37079402001599号

  • 鲁ICP备2022025036号-1
  • Worker 0, 41ms
  • Powered by Hydro v4.9.27 Community