概要

花壇の各区画に対して、区間全体に一様に水を加える（または排水する）操作を \(M\) 回行った後の各区画の水分量を求める問題です。いもす法（累積和の逆操作） を使うことで、区間への加算操作を効率的に処理できます。

考察

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

各作業 \(j\) で区画 \(L_j\) から \(R_j\) まで順に \(D_j\) を加算すると、1回の作業あたり最大 \(O(N)\) の時間がかかります。作業が \(M\) 回あるので、全体で \(O(NM)\) となります。\(N, M\) がともに最大 \(2 \times 10^5\) の場合、\(O(NM) = O(4 \times 10^{10})\) となり、制限時間内に間に合いません。

重要な気づき

各作業は「連続する区間に同じ値を加算する」という操作です。このような区間一様加算を大量に行い、最後にまとめて結果を知りたい場合、いもす法が非常に有効です。

いもす法を使えば、1回の区間加算を \(O(1)\) で記録でき、全作業の記録後に累積和を1回計算するだけで全区画の加算結果が分かります。

アルゴリズム

いもす法の仕組み

長さ \(N+1\) の差分配列 diff を用意し、すべて \(0\) で初期化します。

区画 \(L\) から区画 \(R\) に \(D\) を加算する操作は、差分配列に次のように記録します：

• diff[L-1] += D（区画 \(L\) から効果が始まる）
• diff[R] -= D（区画 \(R\) の次から効果が消える）

具体例: \(N = 5\) で、区画 \(2\) ～ \(4\) に \(+3\) を加算する場合

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

この差分配列の累積和を取ると：

累積: [0, +3, +3, +3, 0, 0]

区画 \(2, 3, 4\) にだけ \(+3\) が加算されていることが分かります。

全体の手順

1. 差分配列 diff を \(N+1\) 要素で初期化
2. \(M\) 回の各作業について、diff[L_j - 1] += D_j、diff[R_j] -= D_j を記録
3. diff の先頭から累積和を取りながら、初期値 \(A_i\) に加算
4. 結果を出力

計算量

• 時間計算量: \(O(N + M)\)
  • 差分配列への記録: 各作業 \(O(1)\) × \(M\) 回 = \(O(M)\)
  • 累積和の計算と初期値への加算: \(O(N)\)
• 空間計算量: \(O(N)\)
  • 差分配列 diff に \(N+1\) 要素

実装のポイント

• 1-indexed と 0-indexed の変換: 問題では区画が \(1\) から始まるが、配列は \(0\) から始まるため、diff[L-1] に加算し diff[R] で減算します。差分配列を \(N+1\) 要素にしておくことで、\(R = N\) のときも範囲外アクセスを防げます。

• 高速な入力: \(N, M\) が大きいので、sys.stdin.buffer.read() でまとめて読み込み、分割する方法が高速です。

• 整数の範囲: 各区画の水分量は最大 \(10^{18}\) に達する可能性がありますが、Python は多倍長整数を標準でサポートしているためオーバーフローの心配はありません（C++ などでは long long を使う必要があります）。

  ソースコード

import sys

def main():
    input_data = sys.stdin.buffer.read().split()
    idx = 0
    N = int(input_data[idx]); idx += 1
    M = int(input_data[idx]); idx += 1
    
    A = [int(input_data[idx + i]) for i in range(N)]
    idx += N
    
    # imos法
    diff = [0] * (N + 1)
    for j in range(M):
        L = int(input_data[idx]); idx += 1
        R = int(input_data[idx]); idx += 1
        D = int(input_data[idx]); idx += 1
        diff[L - 1] += D
        diff[R] -= D
    
    current = 0
    for i in range(N):
        current += diff[i]
        A[i] += current
    
    sys.stdout.write(' '.join(map(str, A)) + '\n')

main()

---

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