当前没有测试数据。

D - 区间加算、問題

得分：$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)$ が「良い」とは、以下の操作を任意の回数（$0$ 回でもよい）行うことで、$X$ の全ての要素を $0$ にできることを言います。

整数 $i$ ($1 \leq i \leq n-K+1$) と、整数 $c$ (負の値も可) を選ぶ。配列 $X_{i}, X_{i+1}, \ldots, X_{i+K-1}$ のそれぞれに $c$ を加える。

ここで、$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$ 行目は、列 $(A_{l_i}, A_{l_i+1}, \ldots, A_{r_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)$ となる。

したがって、最初の行には Yes を出力してください。

一方、列 $(A_2, A_3, A_4, A_5, A_6, A_7) = (-1, 1, -2, 2, 0, 5)$ については、全ての要素を $0$ にする操作の方法が存在しないので、「良い」列ではありません。 したがって、二番目の行には 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