概要

花壇の各区画に初期水分量があり、複数回の範囲更新（水やりまたは排水）を行った後の各区画の最終水分量を求める問題です。

考察

素朴なアプローチでは、各操作に対して区間 \([L_j, R_j]\) の各区画に直接 \(D_j\) を加算する方法が考えられます。しかし、\(N\) と \(M\) が最大 \(2 \times 10^5\) まで大きくなるため、1回の操作で最大 \(2 \times 10^5\) 回の加算、合計 \(M \times (R_j - L_j + 1)\) 回の操作が必要となり、最悪ケースでは \(4 \times 10^{10}\) 回もの計算が必要になってしまいます。これは明らかに時間制限に間に合いません。

そこで、効率的な範囲更新を実現するために「累積和の逆操作」とも言える「遅延評価」の一種である、差分配列を用いた手法が有効です。各操作を差分として記録し、最後に一度だけ累積和を計算することで、範囲更新を効率的に処理できます。

アルゴリズム

1. 差分配列の作成: 長さ \(N+1\) の配列 diff を用意し、すべて0で初期化します。
2. 操作の差分記録: 各操作 \((L_j, R_j, D_j)\) に対して:
   • diff[L_j-1] += D_j
   • diff[R_j] -= D_j （\(R_j\) が最後の区画でない場合）
3. 累積和の計算: diff 配列の先頭から累積和を計算します。これにより、各区画に加算される総水量が得られます。
4. 結果の計算: 初期値 \(A_i\) に累積和で求めた加算量を足し合わせ、最終的な水分量を求めます。

この手法では、各操作を定数時間 \(O(1)\) で処理でき、最後の累積和計算が \(O(N)\) で完了するため、非常に効率的です。

計算量

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

実装のポイント

• 配列のインデックスに注意: 問題では区画番号が1-indexedですが、コードでは0-indexedで処理するため、L_j-1 をインデックスとして使用します。

• 範囲外アクセスの防止: R_j が最後の区画（\(N\)）の場合、diff[R_j] への減算は不要です（配列サイズが \(N+1\) なので、インデックス \(N\) は許容されますが、意味的には不要です）。コードでは if R < N: でチェックしています。

• 一括入力読み込み: 大規模な入力に対応するため、sys.stdin.read で一括読み込みし、高速化を図っています。

  ソースコード

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    
    idx = 0
    N = int(data[idx]); idx += 1
    M = int(data[idx]); idx += 1
    A = list(map(int, data[idx:idx+N])); idx += N
    
    diff = [0] * (N + 1)
    
    for _ in range(M):
        L = int(data[idx]); R = int(data[idx+1]); D = int(data[idx+2]); idx += 3
        diff[L-1] += D
        if R < N:
            diff[R] -= D
            
    current = 0
    result = []
    for i in range(N):
        current += diff[i]
        result.append(str(A[i] + current))
        
    print(" ".join(result))

if __name__ == "__main__":
    main()

この解説は deepseekv3 によって生成されました。