Overview

This is a problem where we need to efficiently compute the resulting array after performing \(M\) operations, each adding the same value \(D_j\) to all elements in the interval \([L_j, R_j]\).

Analysis

If we update every element from section \(L_j\) to \(R_j\) for each operation, a single operation takes up to \(O(N)\) time. In the worst case: - Since \(N, M \le 2 \times 10^5\), - The total is \(O(NM)\), which is around \(4 \times 10^{10}\) — far too slow (TLE).

The key insight here is that “adding a uniform value to an interval” can be recorded in \(O(1)\) per operation using a difference array (the so-called imos method).

For example, when \(N=5\) and we want to add \(+3\) to the interval \([2,4]\): - “The effect of \(+3\) starts at position 2” - “The effect of \(+3\) ends at position 5 (=4+1)” We only need to store this information, without directly updating the elements in between.

Algorithm

Prepare a difference array diff and apply each operation as follows (converting from 1-index to 0-index):

• For operation \((L, R, D)\):
  • diff[L] += D (the increment/decrement starts at \(L\))
  • diff[R] -= D (the increment/decrement ends after \(R\))

By computing the prefix sum of diff from left to right, we obtain the total increment/decrement ultimately added to each section.

The procedure is as follows: 1. Initialize diff as a zero array of length \(N+1\) 2. For each query, perform diff[L-1] += D, diff[R] -= D (this is the key step) 3. Accumulate cur from left to right, updating A[i] += cur to build the answer

The reason diff has length \(N+1\) is to allow writing to diff[N] when diff[R] -= D with \(R=N\) (a sentinel element).

Complexity

• Time complexity: \(O(N + M)\) (each operation is \(O(1)\), plus a final prefix sum in \(O(N)\))
• Space complexity: \(O(N)\) (for the difference array diff)

Implementation Notes

• Since the input \(L, R\) are 1-indexed, we convert by L -= 1 to make it 0-indexed, then perform diff[L] += D, diff[R] -= D (here, R as-is points to the position “one past the right end” in 0-index).

• Values can be as large as \(10^{18}\), so in Python this is handled safely as-is, but in other languages you need 64-bit integers (long long, etc.).

• Finally, by computing the prefix sum cur of diff and adding it to A[i], we obtain the final result.

  Source Code

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

This editorial was generated by gpt-5.2-high.