Range Add Query

题目描述

你得到一个长度为 $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$（可以为负）。对 $K$ 个元素 $X_{i}, X_{i+1}, \ldots, X_{i+K-1}$ 每个加上 $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$，第 $i$ 行应包含 $Yes$ 如果序列 $(A_{l_i}, A_{l_i+1}, \ldots, A_{r_i})$ 是良序列，否则包含 $No$。

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

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

标签: AtCoder|abc288D

来源

AtCoder|abc288D