概要

区間 \([L_i, R_i]\) に同じ値 \(C_i\) を加える操作を \(Q\) 回行ったあと、各位置の合計値をまとめて求める問題です。

考察

各日ごとに「\(L_i\) から \(R_i\) の全プランターに \(C_i\) を加える」を素直に実装すると、1 回の操作で最大 \(N\) 個更新することになり、最悪で \(O(NQ)\) になります。
制約は \(N, Q \le 2 \times 10^5\) なので、\(NQ\) は最大で \(4 \times 10^{10}\) となり、時間内に間に合いません（TLE）。

ここで重要な気づきは、「区間に一括加算」は 差分（増減の境界）だけ記録 すればよい、ということです。

例えば「区間 \([L, R]\) に \(C\) を加える」は、 - \(L\) から先は \(+C\) 増える - ただし \(R+1\) から先では増加を打ち消して \(-C\) する

と考えられます。
つまり配列 diff を用意して - diff[L] += C - diff[R+1] -= C だけ行い、最後に左から累積和を取れば、各プランターの合計が復元できます。

アルゴリズム

1. 長さ \(N+2\) の差分配列 diff を \(0\) で初期化する（\(R+1\) を安全に扱うために余裕を持たせる）。
2. 各クエリ \((L, R, C)\) について以下を行う：
   • diff[L] += C
   • diff[R+1] -= C
3. cur = 0 として \(i=1\) から \(N\) まで順に
   • cur += diff[i]
   • これがプランター \(i\) の最終的な水量
4. 得られた \(N\) 個を出力する。

具体例

\(N=5\)、操作が「\([2,4]\) に \(+3\)」の場合： - diff[2] += 3, diff[5] -= 3

diff の累積和を取ると
位置1: 0
位置2: 3
位置3: 3
位置4: 3
位置5: 0
となり、区間だけが正しく増えることが分かります。

計算量

• 時間計算量: \(O(N + Q)\)（各クエリは \(O(1)\)、最後の累積和が \(O(N)\)）
• 空間計算量: \(O(N)\)（差分配列と結果配列）

実装のポイント

• diff[R+1] を更新するため、配列サイズを N+2 にして範囲外アクセスを避けます。

• 入力が大きいので、Python では sys.stdin.buffer.read() のような高速入力が有効です。

• 本コードでは 1-indexed で扱い、出力用配列だけ 0-indexed に詰めています（res[i-1] = cur）。

  ソースコード

import sys

def main():
    data = list(map(int, sys.stdin.buffer.read().split()))
    if not data:
        return
    N, Q = data[0], data[1]
    diff = [0] * (N + 2)
    idx = 2
    for _ in range(Q):
        L = data[idx]; R = data[idx + 1]; C = data[idx + 2]
        idx += 3
        diff[L] += C
        diff[R + 1] -= C

    res = [0] * N
    cur = 0
    for i in range(1, N + 1):
        cur += diff[i]
        res[i - 1] = cur

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

if __name__ == "__main__":
    main()

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