概要

一列に並んだ花壇に対し、指定された区間に水を複数回やって最終的な水分量を求める問題です。

考察

この問題では、各区間に含まれる花壇の水分量を毎回直接更新すると、最悪の場合 \(O(NQ)\) の計算が必要になり、制約が大きいためTLEしてしまいます。

例えば、区間 \([L_j, R_j]\) に水をやる操作を愚直に行うと、その都度最大 \(N\) 個の要素を更新することになり非効率です。

そこで、差分配列（いもす法）というテクニックを使います。これは、区間への一様な加算を効率的に行うための前処理テクニックです。

具体的には、区間の始点に \(+K\)、終点の次の位置に \(-K\) を記録することで、後で累積和を取ることで各要素への加算回数が求められます。これにより、\(Q\) 回の操作をすべて高速に処理できます。

アルゴリズム

1. 各水やりの区間 \([L_j, R_j]\) に対して、差分配列 diff の \(L_j\) 番目に \(K\) を加算し、\(R_j+1\) 番目から効果を打ち消すために \(-K\) を加算します（0-indexedに変換）。
2. 差分配列の累積和を求めることで、各花壇に何回水がやられたか（＝水分量の増加分）を求めます。
3. 初期の水分量に増加分を足したものが最終的な答えになります。

たとえば、\(N=5\), \(K=10\) で区間 \([2, 4]\) に水をやる場合： - diff[1] += 10 - diff[4] -= 10

累積和を取ると、区間 \([1, 3]\)（0-indexed）にだけ \(10\) が加算された状態になります。

計算量

• 時間計算量: \(O(N + Q)\)
• 空間計算量: \(O(N)\)

実装のポイント

• 区間は1-indexedで入力されるので、0-indexedに変換するのを忘れない。
• 差分配列のサイズは \(N+1\) にしておき、境界処理を簡単にする。
• 最後に累積和を取るときに、前の値を保持しながら更新していくと効率的。

## ソースコード

```python
import sys
input = sys.stdin.read

def main():
    data = input().split()
    idx = 0
    
    N = int(data[idx])
    idx += 1
    K = int(data[idx])
    idx += 1
    Q = int(data[idx])
    idx += 1
    
    C = [int(data[idx + i]) for i in range(N)]
    idx += N
    
    # 差分配列を用意
    diff = [0] * (N + 1)
    
    for _ in range(Q):
        L = int(data[idx]) - 1  # 0-indexedにする
        idx += 1
        R = int(data[idx]) - 1
        idx += 1
        
        diff[L] += K
        diff[R + 1] -= K
    
    # 差分配列から実際の追加分を計算
    added = [0] * N
    current = 0
    for i in range(N):
        current += diff[i]
        added[i] = current
    
    # 最終的な水分量を計算
    result = [C[i] + added[i] for i in range(N)]
    
    print(' '.join(map(str, result)))

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。