分数: 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