概要

\(Q\) 回の区間加算クエリを処理し、最終的な各プランターの水の合計量を求める問題です。いもす法（差分配列）を使うことで効率的に解けます。

考察

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

最も単純な方法は、各クエリで区間 \([L_i, R_i]\) の全要素に \(C_i\) を加算することです。

for 各クエリ (L, R, C):
    for i = L to R:
        water[i] += C

しかし、この方法では1回のクエリで最大 \(O(N)\) の操作が必要です。\(Q\) 回のクエリがあるため、全体で \(O(NQ)\) となり、\(N, Q\) が最大 \(2 \times 10^5\) のとき、\(4 \times 10^{10}\) 回もの操作が必要になりTLE（時間超過）となります。

解決策：いもす法

区間への一様な加算を、始点と終点だけに記録することで \(O(1)\) で処理できます。

具体例: プランター 2〜4 に 3 リットルずつ加える場合（\(N = 5\)）

差分配列の操作： - diff[2] += 3（区間の開始） - diff[5] -= 3（区間の終了の次）

差分配列: [0, 0, +3, 0, 0, -3]

累積和を取ると: [0, 0, 3, 3, 3, 0]

→ プランター 2, 3, 4 にそれぞれ 3 が加算された状態が得られます！

アルゴリズム

1. 差分配列の準備: サイズ \(N+2\) の配列 diff を 0 で初期化
2. クエリの処理: 各クエリ \((L_i, R_i, C_i)\) に対して
   • diff[L_i] += C_i（区間開始位置で増加）
   • diff[R_i + 1] -= C_i（区間終了位置の次で減少）
3. 累積和の計算: diff の累積和を取り、各プランターの水の量を計算

図解:

クエリ: L=2, R=4, C=3 の場合

diff:    [0] [0] [+3] [0] [0] [-3] [0]
index:    0   1    2   3   4    5   6

累積和:  [0] [0] [ 3] [3] [3] [ 0] [0]
         ↑プランター1  ↑2   ↑3  ↑4   ↑5

計算量

• 時間計算量: \(O(N + Q)\)
  • 差分配列の初期化: \(O(N)\)
  • 各クエリの処理: \(O(1) \times Q = O(Q)\)
  • 累積和の計算: \(O(N)\)
• 空間計算量: \(O(N)\)
  • 差分配列と結果配列のサイズ

実装のポイント

1. 配列サイズ: diff のサイズは \(N+2\) にする。\(R_i = N\) のとき diff[R+1] = diff[N+1] にアクセスするため、\(N+1\) までのインデックスが必要。

2. 1-indexed への対応: プランターは 1 から \(N\) の番号が付いているため、累積和の計算は i = 1 から i = N まで行う。

3. 高速な入力: \(Q\) が大きい場合、sys.stdin.readline を使うことで入力を高速化できる。

   ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, Q = map(int, input().split())
    
    # いもす法を使用
    # diff[i] は位置iでの変化量を表す
    diff = [0] * (N + 2)
    
    for _ in range(Q):
        L, R, C = map(int, input().split())
        diff[L] += C
        diff[R + 1] -= C
    
    # 累積和を計算して各プランターの水の量を求める
    result = []
    current = 0
    for i in range(1, N + 1):
        current += diff[i]
        result.append(current)
    
    print(' '.join(map(str, result)))

if __name__ == "__main__":
    main()

---

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