102883: [AtCoder]ABC288 D - Range Add Query

Problem Statement

You are given an integer sequence of length $N$, $A = (A_1, A_2, \ldots, A_N)$, and a positive integer $K$.

For each $i = 1, 2, \ldots, Q$, determine whether a contiguous subsequence of $A$, $(A_{l_i}, A_{l_i+1}, \ldots, A_{r_i})$, is a good sequence.

Here, a sequence of length $n$, $X = (X_1, X_2, \ldots, X_n)$, is good if and only if there is a way to perform the operation below some number of times (possibly zero) to make all elements of $X$ equal $0$.

Choose an integer $i$ such that $1 \leq i \leq n-K+1$ and an integer $c$ (possibly negative). Add $c$ to each of the $K$ elements $X_{i}, X_{i+1}, \ldots, X_{i+K-1}$.

It is guaranteed that $r_i - l_i + 1 \geq K$ for every $i = 1, 2, \ldots, Q$.

Constraints

• $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$
• All values in the input are integers.

Input

The input is given from Standard Input in the following format:

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

Output

Print $Q$ lines. For each $i = 1, 2, \ldots, Q$, the $i$-th line should contain Yes if the sequence $(A_{l_i}, A_{l_i+1}, \ldots, A_{r_i})$ is good, and No otherwise.

Sample Input 1

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

Sample Output 1

Yes
No

The sequence $X \coloneqq (A_1, A_2, A_3, A_4, A_5, A_6) = (3, -1, 1, -2, 2, 0)$ is good. Indeed, you can do the following to make all elements equal $0$.

• First, do the operation with $i = 2, c = 4$, making $X = (3, 3, 5, 2, 2, 0)$.
• Next, do the operation with $i = 3, c = -2$, making $X = (3, 3, 3, 0, 0, 0)$.
• Finally, do the operation with $i = 1, c = -3$, making $X = (0, 0, 0, 0, 0, 0)$.

Thus, the first line should contain Yes.

On the other hand, for the sequence $(A_2, A_3, A_4, A_5, A_6, A_7) = (-1, 1, -2, 2, 0, 5)$, there is no way to make all elements equal $0$, so it is not a good sequence. Thus, the second line should contain No.

Sample Input 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

Sample Output 2

No
Yes
No
Yes
No

问题描述

给你一个长度为 $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$ 加到 $X$ 的 $K$ 个元素 $X_{i}, X_{i+1}, \ldots, X_{i+K-1}$ 上。

保证对于每个 $i = 1, 2, \ldots, Q$，都有 $r_i - l_i + 1 \geq K$。

约束

• $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