概要

\(N\) 個の要素に対して、\(M\) 回の「特定の範囲 \([L, R]\) に値 \(D\) を加算する」という操作を行い、最終的な各要素の値を求める問題です。

考察

素朴なアプローチ

最も単純な方法は、各クエリ（作業）ごとに for ループを回して \(L\) から \(R\) までの範囲に \(D\) を加算することです。 しかし、この方法では \(1\) 回のクエリに最大で \(O(N)\) の時間がかかります。クエリは \(M\) 回あるため、全体の計算量は \(O(NM)\) となります。 制約を見ると \(N, M \leq 2 \times 10^5\) であるため、最悪の場合 \(4 \times 10^{10}\) 回程度の計算が必要になり、実行時間制限（通常 2 秒程度）を大幅に超えてしまいます。

効率的なアプローチ

「範囲に一括で加算し、最後に結果を取得する」という形式の問題では、いもす法（差分更新） を使うのが定石です。 この手法を使うと、各クエリを \(O(1)\) という極めて短い時間で処理でき、最後に \(O(N)\) で全体の状態を復元することができます。

アルゴリズム

いもす法（差分更新）の手順

1. 差分配列の用意: サイズ \(N+1\)（または余裕を持って \(N+2\)）の配列 diff を \(0\) で初期化します。
2. クエリの処理: 範囲 \([L, R]\) に \(D\) を加算する場合、以下の 2 箇所だけを更新します。
   • diff[L] に \(D\) を加える（ここから先は \(D\) 増えるという印）
   • diff[R + 1] から \(D\) を引く（ここから先は \(D\) 増えた分を打ち消すという印）
3. 累積和による復元: すべてのクエリが終わった後、diff 配列の先頭から累積和をとります。
   • current_change = 0 とし、各 \(i\) について current_change += diff[i] を計算します。
   • この current_change が、区画 \(i\) における最終的な増分（合計の \(D\)）になります。
4. 最終結果の計算: 初期状態 \(A_i\) に、復元した増分を加算すれば答えが得られます。

具体例

\(N=5\) で、範囲 \([2, 4]\) に \(10\) を加える場合： - diff[2] += 10 - diff[5] -= 10 (4の次) - 累積和をとると： [0, 10, 10, 10, 0] となり、正しく範囲内だけが \(10\) になります。

計算量

• 時間計算量: \(O(N + M)\)
  • 入力の読み込みに \(O(N + M)\)、クエリ処理に \(O(M)\)、累積和の計算に \(O(N)\) かかります。
• 空間計算量: \(O(N)\)
  • 初期配列 \(A\) と差分配列 diff を保持するために \(O(N)\) のメモリを使用します。

実装のポイント

• 高速な入出力: Python ではデータ量が多い場合、input() を繰り返すと時間がかかるため、sys.stdin.read().split() で一括で読み込むのが効果的です。

• インデックスの管理: 問題文は \(1\)-indexed（1始まり）ですが、Python のリストは \(0\)-indexed です。差分配列のサイズを \(N+2\) にしておくことで、境界条件（\(R+1\)）を気にせずに実装できます。

• 大きな数値の扱い: 最終的な水分量は \(10^{18}\) に達する可能性がありますが、Python は自動的に多倍長整数を扱うため、オーバーフローの心配はありません。”`

  ソースコード

import sys

# 競技プログラミングにおける範囲更新の問題を効率的に解くために、「いもす法（差分配列）」を使用します。
# 各クエリ [L, R] に対して、値 D を加算する操作は以下の2ステップで O(1) で行えます：
# 1. 範囲の開始地点（インデックス L）に D を加算する。
# 2. 範囲の終了地点の次（インデックス R + 1）から D を減算する。
# すべての操作が終わった後、差分配列の累積和（接頭辞和）を計算することで、各要素の最終的な増分を求めることができます。

def solve():
    # 入力を一括で読み込み、スペースで分割してリストにします。
    # Pythonでは input() を繰り返すよりも sys.stdin.read().split() の方が高速です。
    try:
        data = sys.stdin.read().split()
    except EOFError:
        return
    
    if not data:
        return
    
    # N: 区画の数, M: 作業の回数
    N = int(data[0])
    M = int(data[1])
    
    # A: 各区画の初期水分量 (区画1〜N)
    # リスト内包表記を使用して整数に変換します。
    A = [int(x) for x in data[2:2+N]]
    
    # diff: いもす法のための差分配列
    # 1-based indexing（区画番号1〜N）に対応し、R+1 の境界を扱うため、サイズを N+2 とします。
    diff = [0] * (N + 2)
    
    # M 回の作業内容を処理します。
    # 各作業は L (左端), R (右端), D (増減量) の3つの整数で構成されます。
    ptr = 2 + N
    for _ in range(M):
        l = int(data[ptr])
        r = int(data[ptr+1])
        d = int(data[ptr+2])
        ptr += 3
        
        # 範囲 [l, r] に d を加算する操作
        diff[l] += d
        diff[r+1] -= d
        
    # 各区画の最終的な水分量を計算します。
    # current_change は差分配列の累積和であり、その地点での合計増減量を表します。
    current_change = 0
    results = [0] * N
    for i in range(1, N + 1):
        current_change += diff[i]
        # 初期値 A[i-1] に累積の増減量を加算します。
        results[i-1] = A[i-1] + current_change
        
    # 結果をスペース区切りで出力します。
    # 大量のデータを出力する場合、join を使って1つの文字列にしてから出力するのが高速です。
    sys.stdout.write(" ".join(map(str, results)) + "\n")

if __name__ == "__main__":
    solve()

この解説は gemini-3-flash-thinking によって生成されました。