ABC288 D問題 Range Add Query

累積和の考えを利用する

連続する区間に、同じ数字を加える操作をします。これを繰り返すときは、累積和の考え方（「競技プログラミングの鉄則」2.2 一次元の累積和(2) ）が利用できます。
前の数字との差を表す配列を用意すると、 $l$ 番目から連続する $K$ 個の要素に $c$ を加算することは、差の配列の $l$ 番目を $+c$ , $l+K$ 番目を $-c$ することに対応します。
与えられた数列のすべての要素を 0 にすることは、差の配列のすべての要素を 0 にすることと同じです。(差の配列の1番目の要素は、「前の数字」を 0 として、元の数列の1番目の値と同じにします。)

この問題では、連続要素の数 $K$ は固定していますので、要素の何番目かを表す添え字を $K$ で割った余りが異なる要素は互いに影響せず、独立に考えることができます。つまり、差の配列の要素を $K$ で割った余りが $0,1,\cdots,K-1$ のグループに分けて、各グループですべて 0 にできるかを考えればよいです。

元の数列を
$A_1, A_2, \cdots, A_N$
差の配列を
$B_1=A_1$
$B_i = A_i - A_{i-1} ( i = 2,3,\cdots, N)$
と表します。

この $B_i$ を端から 0 にする操作を行います。
まず、1番目の要素に $- B_1$ を加算、 $1+K$ 番目の要素に $+ B_1$ を加算する操作を行います。すると、 $1+K$ 番目の要素は $+ B_1+B_{1+K}$ になります。
これを繰り返していくと、
$1+K$ 番目の要素に $- B_1-B_{1+K}$ を加算、 $1+2K$ 番目の要素に $+ B_1+B_{1+K}$ を加算する操作を行って、
$1+2K$ 番目の要素は $+ B_1+B_{1+K}+B_{2+K}$ になります。
そして、 $1+2K$ 番目の要素に $- B_1-B_{1+K}-B_{1+2K}$ を加算、 $1+3K$ 番目の要素に $+ B_1+B_{1+K}+B_{1+2K}$ を加算する操作を行って、
$1+3K$ 番目の要素は $+ B_1+B_{1+K}+B_{2+K}+B_{1+3K}$ になります。
最終的に、後ろから K番目の要素まで 0 にすることが可能です。このとき、残りの $K-1$ 個の要素がすべて 0 になっていれば「良い数列」であり、 0 でないものが 1個でもあれば「良い数列」ではないことになります。

さらに、この条件は、
$B_p+B_{p+K}+B_{p+2K}+\cdots+B_{p+nK}= \left( A_p-A_{p-1}\right) +\left( A_{p+K}-A_{p+K-1}\right) + \left( A_{p+2K}- A_{p+2K-1}\right) +\cdots+\left( A_{p+nK}-A_{p+nK-1}\right) \\ \left( A_p+ A_{p+K}+ A_{p+2K}+\cdots+A_{p+nK}\right) - \left( A_{p-1} + A_{p+K-1}+ A_{p+2K-1}+\cdots+A_{p+nK-1}\right) \\ = 0$
とも書けるため、
$A_p+ A_{p+K}+ A_{p+2K}+\cdots+A_{p+nK}$ が $p=1,2,\cdots,K$ のすべてのケースで同じ値になっていれば「良い数列」と言えます。

多数のクエリへの対応

この問題は、一つの数列に対して、範囲が異なる多数のクエリを処理します。そのため、さまざまな範囲の和が必要になります。
この部分も累積和（「競技プログラミングの鉄則」2.1 一次元の累積和(1) ）の考え方が利用できます。
$p=1,2,\cdots,K$ として、 $C_p (n)= A_p+A_{p+K}+A_{p+2K}+\cdots+A_{p+nK}$ をあらかじめ計算しておきます。
配列の L 番目から R 番目について問われたとき、
$p+(s-1) K < L \leqq p+s K$ を満たす $s$ と
$p+t K \leqq R < p+(t+1) K$ を満たす $t$
を用いて
$C_p(t)-C_p(s-1)$
がすべての $p$ で同じ値となっているか調べればよいです。

コード例 (Julia)

function solve()

  # 入力
  readInts() =  parse.(Int,split(readline()))
  readInt()  =  parse(Int,readline())

  # 入力データ
  N,K = readInts()
  A = readInts()

  # K とばしの累積和
  C = Vector{Int}(undef,N)

  C[1:K] = A[1:K]

  for i = K+1: N
    C[i] = A[i] + C[i-K]
  end

  # クエリ
  Q = readInt()

  save = -1

  for i = 1:Q
    L, R = readInts()
    ans = "Yes"
    for p = 1: K

      s = cld(L-p,K)  # 割り算,商の小数点以下切り上げ
      t = fld(R-p,K)  # 割り算,商の小数点以下切り捨て

      if p + (s-1)*K > 0
        sum = C[p + t*K] - C[p + (s-1)*K]
      else
        # 求める部分和が 先頭からの和なら C そのままでよい
        sum = C[p + t*K]
      end

      if p == 1
        save = sum
      elseif sum != save
        # 和が一致しない場合があれば、良い配列ではない
        ans = "No"
        break
      end
    end

    println(ans)
  end

end  # function solve

# main
solve()