概要

区間 \([L_j, R_j]\) に同じ値 \(D_j\) を加える操作を \(M\) 回行った後の配列を、高速に求める問題です。

考察

各操作ごとに区画 \(L_j\) から \(R_j\) までを全て更新すると、1 回の操作で最大 \(O(N)\) かかります。すると最悪の場合、 - \(N, M \le 2 \times 10^5\) なので - 合計 \(O(NM)\) となり、\(4 \times 10^{10}\) 程度で到底間に合いません（TLE）。

ここで重要な気づきは、「区間に一様に加算する操作」は 差分配列（いわゆる imos 法）を使うと、各操作を \(O(1)\) で記録できることです。

例えば \(N=5\) のとき、区間 \([2,4]\) に \(+3\) したいなら、 - 「2 から +3 が効き始める」 - 「5（=4+1）から +3 の効果が終わる」 という情報だけ持てばよく、間の要素を直接更新する必要がありません。

アルゴリズム

差分配列 diff を用意して、各操作を次のように反映します（1-index を 0-index に直して扱う）：

• 操作 \((L, R, D)\) に対して
  • diff[L] += D（\(L\) から増減が開始）
  • diff[R] -= D（\(R\) の次から増減が終了）

この diff を左から累積和すると、各区画に最終的に足される総増減量が得られます。

手順は以下です： 1. diff を長さ \(N+1\) の 0 配列で用意 2. 各クエリで diff[L-1] += D, diff[R] -= D を行う（ここが肝） 3. cur を累積しながら A[i] += cur として答えを作る

diff を \(N+1\) にしているのは、diff[R] -= D が \(R=N\) のとき diff[N] に書き込めるようにするためです（番兵）。

計算量

• 時間計算量: \(O(N + M)\)（各操作は \(O(1)\)、最後に累積和で \(O(N)\)）
• 空間計算量: \(O(N)\)（差分配列 diff）

実装のポイント

• 入力の \(L, R\) は 1-index なので、L -= 1 として 0-index に直し、diff[L] += D, diff[R] -= D とします（この R はそのまま 0-index の「右端の次」を指す位置になる）。

• 値は最大で \(10^{18}\) までありうるので、Python ならそのままで安全ですが、他言語なら 64bit 整数（long long など）が必要です。

• 最後は diff の累積和 cur を取りながら A[i] に加えることで、最終結果が得られます。

  ソースコード

import sys

def main():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    A = list(map(int, input().split()))
    diff = [0] * (N + 1)

    for _ in range(M):
        L, R, D = map(int, input().split())
        L -= 1
        diff[L] += D
        diff[R] -= D

    cur = 0
    for i in range(N):
        cur += diff[i]
        A[i] += cur

    sys.stdout.write(" ".join(map(str, A)))

if __name__ == "__main__":
    main()

この解説は gpt-5.2-high によって生成されました。