Overview

This is a problem where you perform multiple addition operations on various intervals of a sequence and determine the final state of the sequence.

Analysis

In this problem, there can be up to \(2 \times 10^5\) elements and operations, so if you naively perform the addition for each interval every time, the worst-case complexity becomes \(O(NM)\), which may exceed the time limit (TLE).

For example, if each operation directly adds \(1\) to all elements in the interval \([L_i, R_i]\), then each operation requires up to \(N\) updates, and the total number of computations can reach up to \(2 \times 10^{10}\).

To address this, we use a technique called the difference array (imos method). This is a preprocessing technique for efficiently performing uniform additions over intervals.

Specifically, the operation of adding value \(x\) to an interval \([L, R]\) is recorded as:

• diff[L] += x
• diff[R+1] -= x

By doing this, each operation completes in constant time \(O(1)\). Afterward, the original array can be reconstructed by taking the prefix sum.

Example:

For instance, suppose \(N = 5\) and the operation is \([1, 3]\).

Initial difference array: [0, 0, 0, 0, 0, 0] (size \(N+1\))

Operation [1, 3] → diff[1] += 1, diff[4] -= 1 → [0, 1, 0, 0, -1, 0]

Applying the prefix sum to this: [0, 1, 1, 1, 0, 0] This means \(1\) has been added to indices \(1\) through \(3\) of the original array (index conversion is needed if using 0-indexed).

In this way, interval updates are processed efficiently.

Algorithm

1. Prepare a difference array diff of length \(N+1\) (to make it easier to handle with 0-indexed).
2. For each operation \([L_i, R_i]\), do the following:
   • diff[L_i - 1] += 1
   • diff[R_i] -= 1
3. Take the prefix sum of diff to reconstruct the original array.

Complexity

• Time complexity: \(O(N + M)\)
• Space complexity: \(O(N)\)

Implementation Notes

• Setting the size of the difference array to \(N+1\) makes boundary handling easier.

• When taking the prefix sum at the end, it is efficient to use a current variable to maintain and update the running value.

• sys.stdin.read is used to read input quickly.

  Source Code

import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    M = int(data[1])
    
    # 差分配列を初期化
    diff = [0] * (N + 1)
    
    index = 2
    for _ in range(M):
        L = int(data[index])
        R = int(data[index + 1])
        index += 2
        
        diff[L - 1] += 1
        diff[R] -= 1
    
    # 差分配列から元の配列を構築
    result = []
    current = 0
    for i in range(N):
        current += diff[i]
        result.append(current)
    
    print(' '.join(map(str, result)))

if __name__ == "__main__":
    main()

---

This editorial was generated by qwen3-coder-480b.