概要

各区画の初期水分量が与えられ、複数回の区間加算操作を行うことで、最終的な各区画の水分量を求めます。

考察

この問題では、各区画に初期値 \(A_i\) があり、それに \(M\) 回の区間更新操作（区間 \([L_j, R_j]\) に \(D_j\) を加える）を適用した後の結果を求める必要があります。

素朴な方法では不十分

もし各操作ごとに区間 \([L_j, R_j]\) のすべての要素を実際に更新してしまうと、最悪の場合で1回の操作に \(O(N)\) かかり、全体で \(O(NM)\) の計算量になってしまいます。
制約より、\(N, M\) は最大で \(2 \times 10^5\) なので、\(O(NM)\) は最大で \(4 \times 10^{10}\) 回の計算が必要となり、明らかに時間内に収まりません（TLE）。

差分更新による高速化

このような「区間に一様に加算」する操作は、いもす法やBIT（Fenwick Tree）、または遅延セグメント木などの技法で効率的に処理できます。
ここでは、いもす法の考え方を用いて、区間の始点と終点+1に加算・減算のイベントを記録し、後で累積和を取ることで各区画の合計変化量を求めています。

具体的には： - 区間 \([L, R]\) に \(D\) を加える操作は、位置 \(L\) に \(+D\)、位置 \(R+1\) に \(-D\) のイベントとして記録します。 - 最後に左から右へスキャンしながら、現在の変化量の合計を保持し、初期値に加えることで答えを得ます。

これにより、各操作は定数時間で処理でき、全体で \(O(N + M)\) で解くことができます。

アルゴリズム

1. 各操作 \(j\) について、区間 \([L_j, R_j]\) に \(D_j\) を加算するという情報を、差分として記録します：

   • 位置 \(L_j\) に \(+D_j\)
   • 位置 \(R_j + 1\) に \(-D_j\)

2. 各位置 \(i\) に対して、その時点で加算されるべき差分の合計を計算します（いもす法の要領）。

3. 各区画の最終的な水分量は、初期値 \(A_i\) にその区画での差分の累積和を足したものになります。

この処理は、BITを使わずとも、配列上で前処理と累積和の計算を行うことで実現できます。

計算量

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

実装のポイント

• 操作の情報（\(L, R, D\)）を前処理でイベントリストに変換し、開始位置と終了位置+1に加算・減算を記録します。
• 累積和のように現在の変化量を保持しながら、初期値に加えて答えを構築します。
• Pythonでは高速な入力処理（sys.stdin.readなど）を使うことで、大きな入力にも耐えられるようにします。

## ソースコード

```python
import sys
input = sys.stdin.read

class BIT:
    def __init__(self, n):
        self.n = n
        self.tree = [0] * (n + 1)
    
    def add(self, i, x):
        while i <= self.n:
            self.tree[i] += x
            i += i & -i
    
    def sum(self, i):
        s = 0
        while i > 0:
            s += self.tree[i]
            i -= i & -i
        return s

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 = [0] * (N + 1)
    for i in range(1, N + 1):
        A[i] = int(data[idx])
        idx += 1
    
    # 座標圧縮のためのイベントリスト
    events = []
    for i in range(M):
        L = int(data[idx])
        idx += 1
        R = int(data[idx])
        idx += 1
        D = int(data[idx])
        idx += 1
        events.append((L, D))
        events.append((R+1, -D))
    
    # BITの準備
    bit = BIT(N)
    
    # 各作業を処理
    # イベントをソートして処理する
    # しかし、ここでは直接差分をBITに載せる
    
    # 初期化: 各位置への加算クエリを記録
    updates = [[] for _ in range(N+2)]
    idx = 2 + N
    for j in range(M):
        L = int(data[idx])
        idx += 1
        R = int(data[idx])
        idx += 1
        D = int(data[idx])
        idx += 1
        updates[L].append(D)
        updates[R+1].append(-D)
    
    result = [0] * (N+1)
    current = 0
    for i in range(1, N+1):
        for d in updates[i]:
            current += d
        result[i] = A[i] + current
    
    print(' '.join(map(str, result[1:])))

if __name__ == "__main__":
    main()

この解説は qwen3-coder-480b によって生成されました。