概要

\(N\) 個のプランターに、\(Q\) 回の操作で指定された区間に水をあげるとき、最終的に各プランターに与えられた水の総量を求める問題。

考察

この問題では、各クエリで「ある区間のすべての要素に同じ値を加算する」という操作が繰り返されます。例えば、プランター \(L\) から \(R\) までに \(C\) リットルずつ水をやるという操作は、配列の添字 \(L-1\) から \(R-1\) までの要素すべてに \(C\) を足す操作に対応します（0-indexedに変換）。

素朴な方法として、「各クエリごとに実際に区間に対して値を足していく」ことが考えられます。しかし、この方法では最悪の場合、1回のクエリで最大 \(N\) 個の要素を更新する必要があり、全体で \(O(NQ)\) の計算量がかかります。制約が \(N, Q \leq 2 \times 10^5\) であるため、これは時間内に処理できません（\(10^{10}\) オーダーの計算が必要）。

そこで登場するのが「差分配列（いもす法）」というテクニックです。差分配列を使うことで、区間への一様加算を定数時間で処理できます。

たとえば、配列 \(A\) の区間 \([L, R]\) すべてに値 \(C\) を加える操作は、差分配列 \(diff\) を用いて以下のように表現できます： - \(diff[L] \mathrel{+}= C\) - \(diff[R+1] \mathrel{-}= C\)

そして最後に、\(diff\) の累積和を取ることで、元の配列を得ることができます。

この方法を使えば、各クエリを \(O(1)\) で処理でき、最後に累積和を取るステップが \(O(N)\) なので、全体で \(O(N + Q)\) で解くことができます。

アルゴリズム

1. 配列 diff をサイズ \(N+1\) で用意する（1-indexedで扱うため、境界処理のために1つ多く確保）。
2. 各クエリ \((L_i, R_i, C_i)\) に対して、以下のように差分を記録する：
   • diff[L_i - 1] += C_i
   • diff[R_i] -= C_i
3. diff の累積和を取り、各プランターに与えられた水の量を計算する。

計算量

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

実装のポイント

• 入力を高速に読み込むために sys.stdin.read() を使用している（Pythonでは重要）。
• 差分配列の添字管理に注意：1-indexedの入力を0-indexedに変換する。
• 最後に累積和を取るときに、結果をリストに保存して一度に空白区切りで出力すると効率的。

## ソースコード

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

def main():
    data = input().split()
    N = int(data[0])
    Q = int(data[1])
    
    # 差分配列を用意
    diff = [0] * (N + 1)
    
    index = 2
    for _ in range(Q):
        L = int(data[index])
        R = int(data[index+1])
        C = int(data[index+2])
        index += 3
        
        # 1-indexed なので、0-indexed に変換
        diff[L-1] += C
        diff[R] -= C
    
    # 差分配列から元の配列を構築
    result = []
    current = 0
    for i in range(N):
        current += diff[i]
        result.append(current)
    
    print(' '.join(map(str, result)))

if __name__ == "__main__":
    main()

---

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