概要

連続した範囲への加算クエリが複数回与えられるので、すべての操作後の各要素の値を求める問題です。「いもす法」を使うことで効率的に解くことができます。

考察

素朴なアプローチの問題点

愚直に考えると、各水やりクエリ \((L_j, R_j)\) に対して、\(L_j\) から \(R_j\) までの花壇すべてに \(K\) を加算する方法が思いつきます。

for j in range(Q):
    for i in range(L[j], R[j]+1):
        C[i] += K

しかし、この方法の計算量は最悪 \(O(N \times Q)\) となります。\(N, Q\) がともに最大 \(2 \times 10^5\) の場合、\(4 \times 10^{10}\) 回の操作が必要となり、TLE（実行時間超過）になります。

重要な気づき

各クエリで「何回水をやったか」という 回数 だけを記録しておき、最後にまとめて \(K\) を掛ければよいことに気づきます。つまり、各花壇 \(i\) について「水やりされた回数」を求め、最後に \(C_i + (\text{回数}) \times K\) を計算すればOKです。

この「区間への加算を効率的に処理する」手法として いもす法 が使えます。

アルゴリズム

いもす法とは

区間 \([L, R]\) への加算を、差分配列 を使って \(O(1)\) で記録し、最後に累積和を取ることで各位置の値を復元する手法です。

具体的には： 1. 差分配列 diff を用意する（初期値はすべて0） 2. 区間 \([L, R]\) に +1 したいとき： - diff[L] += 1（この位置から +1 が始まる） - diff[R+1] -= 1（この位置で +1 が終わる） 3. 最後に diff の累積和を取ると、各位置への加算回数が得られる

具体例

\(N = 5\) で、区間 \([2, 4]\) と \([3, 5]\) に水をやる場合：

初期:  diff = [0, 0, 0, 0, 0, 0]  (サイズ N+1)

[2,4]に+1:  diff[1] += 1, diff[4] -= 1
           diff = [0, 1, 0, 0, -1, 0]

[3,5]に+1:  diff[2] += 1, diff[5] -= 1
           diff = [0, 1, 1, 0, -1, -1]

累積和:    count = [0, 1, 2, 2, 1, 0]
           → 花壇1は1回、花壇2は2回、花壇3は2回、花壇4は1回、花壇5は0回

（※ 0-indexed の場合。コードでは L-1 と R を使用）

計算量

• 時間計算量: \(O(N + Q)\)
  • 各クエリの処理: \(O(1) \times Q = O(Q)\)
  • 累積和の計算と結果の出力: \(O(N)\)
• 空間計算量: \(O(N)\)
  • 差分配列 diff と結果配列 result に \(O(N)\)

実装のポイント

1. インデックスの変換: 問題では花壇は1-indexedですが、Pythonの配列は0-indexedなので、diff[L-1] と diff[R] を使います。

2. 差分配列のサイズ: diff[R] にアクセスするため、サイズは \(N+1\) 必要です（\(R\) が \(N\) のとき diff[N] にアクセスするため）。

3. オーバーフロー対策: \(K\) と水やり回数の積が大きくなる可能性がありますが、Pythonでは整数のオーバーフローがないため心配不要です。

4. 高速な入力: \(N, Q\) が大きいため、sys.stdin.read() でまとめて読み込むと高速になります。

   ソースコード

import sys

def main():
    input_data = sys.stdin.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    K = int(input_data[idx]); idx += 1
    Q = int(input_data[idx]); idx += 1
    
    C = [int(input_data[idx + i]) for i in range(N)]
    idx += N
    
    # いもす法用の差分配列
    diff = [0] * (N + 1)
    
    for _ in range(Q):
        L = int(input_data[idx]); idx += 1
        R = int(input_data[idx]); idx += 1
        diff[L - 1] += 1
        diff[R] -= 1
    
    # 累積和を計算して各花壇への水やり回数を求める
    count = 0
    result = []
    for i in range(N):
        count += diff[i]
        result.append(C[i] + count * K)
    
    print(' '.join(map(str, result)))

if __name__ == '__main__':
    main()

---

この解説は claude4.5opus によって生成されました。