← 返回题目列表

AtCoder · abc288_d

G. 范围添加查询

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

分数: 400 点

问题陈述

给你一个长度的整数序列 N, A = (A_1, A_2, \ldots, A_N),和一个正整数 K.

对于每个 i = 1, 2, \ldots, Q,判断是否为连续子序列 A, (A_{l_i}, A_{l_i+1}, \ldots, A_{r_i}),是一个 好的序列.

这里,长度序列 n, X = (X_1, X_2, \ldots, X_n)是 好 当且仅当有一种方法可以执行低于一定次数(可能为零)的操作以使所有元素 X 等于 0.

选择一个整数 i 这样 1 \leq i \leq n-K+1 和一个整数 c (可能为负)。添加 c 到每个 K 元素 X_{i}, X_{i+1}, \ldots, X_{i+K-1}.

保证 r_i - l_i + 1 \geq K 对于每个 i = 1, 2, \ldots, Q.

约束

  • 1 \leq N \leq 2 \times 10^5
  • 1 \leq K \leq \min\lbrace 10, N \rbrace
  • -10^9 \leq A_i \leq 10^9
  • 1 \leq Q \leq 2 \times 10^5
  • 1 \leq l_i, r_i \leq N
  • r_i-l_i+1 \geq K
  • 输入中的所有值都是整数。

输入

输入由标准输入按以下格式给出:

N K
A_1 A_2 \ldots A_N
Q
l_1 r_1
l_2 r_2
\vdots
l_Q r_Q

输出

打印 您选择的 Q 行。 对于每个 i = 1, 2, \ldots, Q, i- 第行应包含 Yes 如果序列 (A_{l_i}, A_{l_i+1}, \ldots, A_{r_i}) 很好,并且 No 否则。


示例输入 1

7 3
3 -1 1 -2 2 0 5
2
1 6
2 7

示例输出 1

Yes
No

序列 X \coloneqq (A_1, A_2, A_3, A_4, A_5, A_6) = (3, -1, 1, -2, 2, 0) 很好。 事实上,您可以执行以下操作以使所有元素相等 0.

  • 首先,执行操作 i = 2, c = 4, 制作 X = (3, 3, 5, 2, 2, 0).
  • 接下来,执行操作 i = 3, c = -2, 制作 X = (3, 3, 3, 0, 0, 0).
  • 最后,执行操作 i = 1, c = -3, 制作 X = (0, 0, 0, 0, 0, 0).

因此,第一行应包含 Yes.

另一方面,对于序列 (A_2, A_3, A_4, A_5, A_6, A_7) = (-1, 1, -2, 2, 0, 5),无法使所有元素相等 0,所以这不是一个好的序列。 因此,第二行应该包含 No.


示例输入 2

20 4
-19 -66 -99 16 18 33 32 28 26 11 12 0 -16 4 21 21 37 17 55 -19
5
13 16
4 11
3 12
13 18
4 10

示例输出 2

No
Yes
No
Yes
No