Overview

Given \(N\) elements (initially \(0\)), perform \(M\) operations that add \(1\) to a specified range \([L, R]\), and determine the final state of the sequence.

Analysis

Naive Approach

For each operation, one could loop through the sequence from the \(L\)-th to the \(R\)-th element and increment each one by one. However, this method takes up to \(O(N)\) time per operation. Since there are \(M\) operations, the overall time complexity is \(O(NM)\). Given the constraints of this problem where \(N, M \leq 2 \times 10^5\), we get \(N \times M \approx 4 \times 10^{10}\), which far exceeds typical time limits (around 2 seconds) and results in TLE (Time Limit Exceeded).

Efficient Approach

To optimize the operation of “uniformly adding to an entire range,” we use a technique called “imos method (difference array)”. In this technique, instead of updating every element in the range, we only record two positions: the “start of the range” and “just after the end of the range”. This allows each operation to be processed in \(O(1)\).

Algorithm

Steps of the Imos Method

1. Prepare the difference array: Create an array diff of length \(N+1\) (or \(N+2\) for safety) and initialize all elements to \(0\).
2. Schedule additions (query processing): For each operation \([L, R]\), do the following:
   • Add \(1\) to diff[L] (a marker indicating the value increases by \(1\) starting here).
   • Subtract \(1\) from diff[R + 1] (a marker indicating the value decreases by \(1\) starting here, i.e., the increment is cancelled out).
3. Compute the prefix sum: Take the prefix sum of the diff array from left to right.
   • The final value of the \(i\)-th element is \(\sum_{k=1}^{i} diff[k]\).

Concrete Example

For \(N=5\), adding \(1\) to the range \([2, 4]\): - diff[2] += 1 - diff[5] -= 1 (\(R+1 = 5\)) - State of the diff array: [0, 0, 1, 0, 0, -1] - Taking the prefix sum: [0, 0, 1, 1, 1, 0] - As a result, the 2nd through 4th elements become \(1\).

Complexity

• Time complexity: \(O(N + M)\)
  • Processing \(M\) queries takes \(O(M)\), and computing the final prefix sum takes \(O(N)\).
  • For \(N, M = 2 \times 10^5\), this requires only about \(4 \times 10^5\) operations, which is sufficiently fast.
• Space complexity: \(O(N)\)
  • The diff array for maintaining the sequence state and the result array use \(O(N)\) memory.

Implementation Notes

• Fast I/O: Since \(N, M\) can be large, in Python it is faster to read all input at once using sys.stdin.read().split() rather than calling input() repeatedly.

• Array size: Since we access diff[R + 1], the array size must be at least \(N+1\).

• Index handling: The problem uses \(1\)-indexed (1-based) numbering, but Python lists are \(0\)-indexed. In the code, we allocate diff with extra size to handle it as \(1\)-indexed directly, and adjust during output.

  Source Code

import sys

def solve():
    # 標準入力から全てのデータを読み込む
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    M = int(input_data[1])
    
    # いもす法（累積和）を用いるための差分配列を用意
    # インデックスは1からNまでをカバーし、R+1の操作のためにサイズN+2を確保
    diff = [0] * (N + 2)
    
    # 各クエリに対して差分配列を更新
    for i in range(M):
        L = int(input_data[2 + 2 * i])
        R = int(input_data[3 + 2 * i])
        diff[L] += 1
        diff[R + 1] -= 1
    
    # 累積和を計算して各要素の最終的な値を求める
    ans = [0] * N
    current_val = 0
    for i in range(1, N + 1):
        current_val += diff[i]
        ans[i - 1] = current_val
    
    # 結果をスペース区切りで出力
    sys.stdout.write(" ".join(map(str, ans)) + "\n")

if __name__ == '__main__':
    solve()

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