Overview

Given \(N\) lights, this problem asks you to perform \(M\) operations, each toggling the switches of lights within a specified interval, and then determine the number of lights that are on at the end.

Analysis

The state of each light is determined by “how many times its switch has been toggled in total.” Since all lights are initially off, a light is on if toggled an odd number of times and off if toggled an even number of times.

A naive approach would be to loop through each light from \(L_j\) to \(R_j\) and flip it for each operation. However, this method takes up to \(O(N)\) time per operation, resulting in an overall time complexity of \(O(NM)\). Given the constraints (\(N \leq 10^6, M \leq 2 \times 10^5\)), the worst case would require approximately \(2 \times 10^{11}\) operations, which would result in a Time Limit Exceeded (TLE) verdict.

To solve this efficiently, we use a technique called the imos method (difference array), which performs range additions quickly. With the imos method, each range update can be done in \(O(1)\), and the total toggle counts for all lights can be computed in \(O(N)\) at the end.

Algorithm

Using the imos method, we compute the number of times each light’s switch has been toggled with the following steps:

1. Prepare the difference array Create an array diff of length \(N+2\), initialized entirely to \(0\). (We use 1-indexed access and need to access index \(R_j + 1\), so a size of \(N+2\) is used.)

2. Update only the endpoints of each interval For the \(j\)-th operation toggling the interval \([L_j, R_j]\), perform the following additions and subtractions:

   • Add \(1\) to diff[L_j] (meaning the toggle count increases by \(+1\) starting here)
   • Subtract \(1\) from diff[R_j + 1] (meaning the increase in toggle count ends here)

Example: For \(N=5\) and an operation on interval \([2, 4]\), add \(+1\) to diff[2] and \(-1\) to diff[5].

1. Compute the prefix sum After all operations are complete, compute the prefix sum of diff from left to right. The prefix sum value at light \(i\) represents the total number of times that light’s switch has been toggled.

Continuing the example: After computing the prefix sum, the values at indices 1, 2, 3, 4, 5 are 0, 1, 1, 1, 0 respectively, correctly showing that \(1\) has been added to the interval \([2, 4]\).

1. Count the lights that are on Count the number of lights whose computed prefix sum is odd (curr % 2 != 0), and output that count as the answer.

Complexity

• Time complexity: \(O(N + M)\)
  • \(O(M)\) for the additions and subtractions to the difference array (\(M\) operations)
  • \(O(N)\) for computing the prefix sum and counting the answer
  • Overall, this runs very efficiently and comfortably fits within the time limit.
• Space complexity: \(O(N)\)
  • Memory is used to store the diff array of length \(N+2\).

Implementation Notes

• Fast input: In Python, calling input() many times can cause delays. Therefore, we use sys.stdin.read().split() to read all input at once and convert it to a list for processing, which significantly speeds things up.

• Preventing out-of-bounds access: When \(R_j = N\), diff[R_j + 1] accesses diff[N + 1]. To prevent an out-of-bounds error (IndexError), it is safe to allocate the array with size \(N+2\) rather than \(N+1\).

  Source Code

import sys

def main():
    input_data = sys.stdin.read().split()
    if not input_data:
        return
    
    N = int(input_data[0])
    M = int(input_data[1])
    
    diff = [0] * (N + 2)
    
    idx = 2
    for _ in range(M):
        l = int(input_data[idx])
        r = int(input_data[idx+1])
        diff[l] += 1
        diff[r + 1] -= 1
        idx += 2
        
    ans = 0
    curr = 0
    for i in range(1, N + 1):
        curr += diff[i]
        if curr % 2 != 0:
            ans += 1
            
    print(ans)

if __name__ == '__main__':
    main()

This editorial was generated by gemini-3.1-pro-thinking.