Overview

This is a problem where you perform multiple range addition operations on a sequence and determine the final value of each element.

Analysis

A naive approach would be to add 1 to every element in the specified range \([L_i, R_i]\) for each operation. However, since \(N\) and \(M\) can be up to \(2 \times 10^5\), updating up to \(2 \times 10^5\) elements per operation would require \(2 \times 10^5 \times 2 \times 10^5 = 4 \times 10^{10}\) operations in the worst case, which would not fit within the time limit.

To solve this problem efficiently, we use a technique called the “Imos method” (difference array technique), which can process range additions in constant time. In the Imos method, each operation marks the start position and the position right after the end position, allowing us to compute the final values of all elements with a single scan.

Algorithm

The steps of the Imos method are as follows:

1. Initialize an array diff of length \(N+2\) with zeros (we use +2 because we handle indices in 1-based indexing).
2. For each operation \((L_i, R_i)\):
   • Add +1 to diff[L_i]
   • Add -1 to diff[R_i + 1]
3. Compute the prefix sum of the array diff from the beginning. This prefix sum gives the final value of each element.

Let’s illustrate with an example. For \(N=5\), \(M=2\), with operations \((1, 3)\) and \((2, 4)\): - Operation 1: diff[1] += 1, diff[4] -= 1 - Operation 2: diff[2] += 1, diff[5] -= 1 - Compute the prefix sum: - index1: 0 + 1 = 1 - index2: 1 + 1 = 2 - index3: 2 + 0 = 2 - index4: 2 - 1 = 1 - index5: 1 - 1 = 0 - Result: [1, 2, 2, 1, 0]

Complexity

• Time complexity: \(O(N + M)\)
  • Each operation is processed in \(O(1)\), and the prefix sum computation takes \(O(N)\)
• Space complexity: \(O(N)\)
  • The difference array uses \(O(N)\) memory

Implementation Notes

• Since we handle array indices in 1-based indexing, we allocate the array with size \(N+2\) (to allow access up to \(N+1\) for \(R_i+1\))

• Reading input data in bulk enables faster processing

• When computing the prefix sum, we use a variable current to hold the running total, adding the difference array value at each position

• Pay attention to the output format: convert the numbers to strings and output them separated by spaces

  Source Code

import sys

def main():
    data = sys.stdin.read().split()
    n = int(data[0])
    m = int(data[1])
    
    diff = [0] * (n + 2)
    
    index = 2
    for _ in range(m):
        l = int(data[index])
        r = int(data[index + 1])
        index += 2
        diff[l] += 1
        diff[r + 1] -= 1
    
    current = 0
    result = []
    for i in range(1, n + 1):
        current += diff[i]
        result.append(str(current))
    
    print(" ".join(result))

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.