区间加查询

题目描述

给定长度为 $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)$ 是「好的」,当且仅当存在一种方法,通过进行下面操作若干次(可能为 0 次),使 $X$ 的所有元素都变为 $0$。

选择满足 $1 \leq i \leq n-K+1$ 的整数 $i$ 和整数 $c$(可以为负)。将 $X_{i}, X_{i+1}, \ldots, X_{i+K-1}$ 这 $K$ 个元素分别加上 $c$。

保证对每个 $i = 1, 2, \ldots, Q$,都有 $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$,若序列 $(A_{l_i}, A_{l_i+1}, \ldots, A_{r_i})$ 是好的,第 $i$ 行输出 Yes,否则输出 No。

样例

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

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)$。

因此,第 1 行应输出 Yes。

另一方面,序列 $(A_2, A_3, A_4, A_5, A_6, A_7) = (-1, 1, -2, 2, 0, 5)$ 不存在使其所有元素变为 $0$ 的方法,因此它不是好的序列。

因此,第 2 行应输出 No。

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

No
Yes
No
Yes
No

数据范围

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