Overview

Given \(N\) elements, perform \(M\) operations of “add value \(D\) to a specific range \([L, R]\)”, and find the final value of each element.

Analysis

Naive Approach

The simplest method is to use a for loop for each query (operation) to add \(D\) to the range from \(L\) to \(R\). However, this method takes up to \(O(N)\) time per query. Since there are \(M\) queries, the total time complexity is \(O(NM)\). Looking at the constraints, \(N, M \leq 2 \times 10^5\), so in the worst case approximately \(4 \times 10^{10}\) operations are needed, which far exceeds the time limit (typically around 2 seconds).

Efficient Approach

For problems of the form “add to a range in bulk and retrieve the results at the end,” the standard technique is the imos method (difference array update). Using this technique, each query can be processed in \(O(1)\) time, and the entire state can be reconstructed in \(O(N)\) at the end.

Algorithm

Steps of the Imos Method (Difference Array Update)

1. Prepare a difference array: Initialize an array diff of size \(N+1\) (or \(N+2\) for safety) with \(0\).
2. Process queries: To add \(D\) to the range \([L, R]\), update only the following 2 positions:
   • Add \(D\) to diff[L] (a marker meaning “from here onward, increase by \(D\)”)
   • Subtract \(D\) from diff[R + 1] (a marker meaning “from here onward, cancel the increase of \(D\)”)
3. Reconstruct using prefix sums: After all queries are processed, compute the prefix sum of the diff array from the beginning.
   • Set current_change = 0, and for each \(i\), compute current_change += diff[i].
   • This current_change is the final increment (total \(D\)) for position \(i\).
4. Compute the final result: Add the reconstructed increment to the initial value \(A_i\) to obtain the answer.

Concrete Example

For \(N=5\), adding \(10\) to the range \([2, 4]\): - diff[2] += 10 - diff[5] -= 10 (one past index 4) - Taking the prefix sum gives: [0, 10, 10, 10, 0], correctly applying \(10\) only within the range.

Complexity

• Time complexity: \(O(N + M)\)
  • Reading input takes \(O(N + M)\), processing queries takes \(O(M)\), and computing the prefix sum takes \(O(N)\).
• Space complexity: \(O(N)\)
  • \(O(N)\) memory is used to store the initial array \(A\) and the difference array diff.

Implementation Notes

• Fast I/O: In Python, when the amount of data is large, repeatedly calling input() is slow, so it is effective to read all input at once using sys.stdin.read().split().

• Index management: The problem uses \(1\)-indexed (starting from 1), but Python lists are \(0\)-indexed. By setting the difference array size to \(N+2\), you can implement without worrying about boundary conditions (\(R+1\)).

• Handling large numbers: The final values can reach up to \(10^{18}\), but since Python automatically handles arbitrary-precision integers, there is no concern about overflow.

  Source Code

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()

This editorial was generated by gemini-3-flash-thinking.