まず、数列 \(X = (X_1, X_2, \ldots, X_n)\) が良い数列であるための必要十分条件を考えます。

\(X_0 \coloneqq 0, X_{n+1} \coloneqq 0\) として、\((X_0, X_1, X_2, \ldots, X_n, X_{n+1})\) の階差数列 \(X' = (X'_0, X'_1, \ldots, X'_n)\) を考えます。ここで、\(X'_i = X_{i+1} - X_i\) です。 このとき、\(X\) の連続する \(K\) 要素 \(X_i, X_{i+1}, \ldots, X_{i+K-1}\) に整数 \(c\) を加算して

\[(X_0, X_1, \ldots, X_{i-1}, \red{X_i+c, X_{i+1}+c, \ldots, X_{i+K-1}+c}, X_{i+K}, \ldots, X_n, X_{n+1})\]

とする操作は、対応する階差数列 \(X'\) では、

\[ (X'_0, X'_1, \ldots, \red{X'_{i-1} + c}, X'_i, X'_{i+1}, \ldots, \red{X'_{i+K-1}-c}, X'_{i+K}, \ldots, X'_n)\]

の通り、\(X'_{i-1}\) に \(c\) を \(X'_{i+K-1}\) に \(-c\) を加算する操作に対応しています。 また、\(X\) のすべての要素が \(0\) であることと \(X'\) のすべての要素が \(0\) であることは同値です。 したがって、\(X\) が良い数列であることは、下記の操作を繰り返して \(X'\) のすべての要素を \(0\) にできることと同値です。

\((\star)\) \(0 \leq i \leq n-K\) を満たす整数 \(i\) および、整数 \(c\) を選び、\(X'_i\) に \(c\) を、\(X'_{i+K}\) に \(-c\) をそれぞれ加算する。

ここで、\(X'\) の要素を添字を \(K\) で割ったあまりによって \(K\) 個のグループに分けます。 上記の操作 (\(\star\)) を繰り返すと、各 \(r = 0, 1, \ldots, K-1\) について、余り \(r\) に対応するグループの各要素 \(X'_r, X'_{K+r}, X'_{2K+r}, \ldots, X'_{h_rK+r}\) （ただし \(h_r \coloneqq \lfloor \frac{n-r}{K} \rfloor\) ）の値を、これらの総和 \(\sum_{i = 0} ^{h_r} X'_{iK+r}\) を変えない範囲で自由に変更することができます。

したがって、\(X'\) の要素をすべて \(0\) にできること（つまり、\(X\) が良い数列であること）は、すべての余り \(r = 0, 1, \ldots, K-1\) について、\(\sum_{i = 0} ^{h_r} X'_{iK+r} = 0\) が成り立つことと同値です。

以上から、与えられた数列 \(X\) が良い数列かを判定するには、その階差数列 \(X'\) の要素を添字を \(K\) で割ったあまりでグループ分けし、各グループの要素の総和が \(0\) かどうかを判定すれば良いことがわかりました。

しかし、これを入力で与えられる各 \((l_i, r_i)\) ごとに愚直に行うと、 一つの \((l_i, r_i)\) に対して最悪 \(\Theta(N)\) 時間かかるため、アルゴリズム全体で最悪 \(\Theta(QN)\) 時間かかり、実行制限時間に間に合わせることが絶望的です。そのため、これを高速化した以下の手順を行います。

• まず、入力で与えられた数列 \(A\) に対して、 \(A_0 \coloneqq 0, A_{N+1} \coloneqq 0\)として、\((A_0, A_1, A_2, \ldots, A_N, A_{N+1})\) の階差数列 \(A' = (A'_0, A'_1, \ldots, A'_N)\) を計算します。ここで、\(A'_i = A_{i+1} - A_i\) です。

• 次に、\(A'\) の要素を添字を \(K\) で割った余りでグループ分けし、 \(K\) で割った余りごとの累積和配列 \(S = (S_0, S_1, \ldots, S_N)\) 、すなわち、\(S_i \coloneqq A'_r + A'_{K+r} + \cdots + A'_{i-r} + A'_i\) で定まる配列 \(S\) を求めます。これは、\(S_i = S_{i-r} + A'_i\) の関係を用いると全体で \(O(N)\) 時間で求められます。

• その後、与えられた \(Q\) 個の各連続部分列 \((A_l, A_{l+1}, \ldots, A_r)\) が良い数列かどうかを、前計算した累積和配列 \(S\) を用いて判定します。 \((X_0, X_1, \ldots, X_n, X_{n+1}) \coloneqq (0, A_l, A_{l+1}, \ldots, A_r, 0)\) の階差数列 \(X'\) は \((X'_0, X'_1, \ldots, X'_n) = (A'_{l-1}\red{+A_{l-1}}, A'_l, \ldots, A'_r\red{ - A_{r+1}})\) です。 これは、ほとんど \((A'_{l-1}, A'_l, \ldots, A'_r)\) という形をしていることに注意してください。 各 \(r = 0, 1, \ldots, K-1\) について、\(A'_{aK+r} + A'_{(a+1)K+r} + \cdots + A'_{bK+r}\) という形の和は前計算した累積和配列 \(S\) を用いて \(S_{bK+r} - S_{(a-1)K+r}\) と表せることを用いると、 \(\sum_{i = 0} ^{h_r} X'_{iK+r} = 0\) が成り立つかどうかを各 \(r = 0, 1, \ldots, K-1\) について \(O(1)\) 時間で計算でき、\((A_l, A_{l+1}, \ldots, A_r)\) が良い数列かどうかの判定全体を \(O(K)\) 時間で行うことができます。

以上より、本問題を \(O(N + QK)\) 時間で解くことができます。