Overview

This problem asks us to find the number of lights that are ultimately turned on after performing \(M\) operations, each of which toggles the switches of all lights within a given interval.

Analysis

In this problem, for each interval \([L_j, R_j]\), we flip the state (on/off) of all lights belonging to it. A naive approach that updates each light one by one for every operation would require \(O(N \times M)\) computations in the worst case. Under the constraints \(N \leq 10^6\), \(M \leq 2 \times 10^5\), this cannot be processed within the time limit (requiring up to \(2 \times 10^{11}\) computations).

The key insight here is to focus only on “how many times each light’s switch was pressed.” If a switch is pressed an even number of times, it returns to its original state (off), and if pressed an odd number of times, it is on. Therefore, what we need is to “efficiently perform addition over each interval and determine how many times each light was operated on at the end.”

This can be efficiently handled using a difference array (also known as the imos method). By recording the increment over an interval \([L, R]\) in difference form, we can obtain the value of each element by computing the prefix sum at the end.

For example, if there are 4 lights and we perform an operation on the interval \([2, 3]\), we record the following in the difference array: - diff[2] += 1 - diff[4] -= 1

Then, by computing the prefix sum of diff, we obtain the number of operations applied to each light.

Algorithm

1. Prepare a difference array diff of length \(N+2\) (extra space for boundary handling).
2. For each operation \([L_j, R_j]\):
   • diff[L_j] += 1
   • diff[R_j + 1] -= 1
3. Compute the prefix sum of the difference array to determine the number of operations for each light.
4. Count the number of lights whose operation count is odd.

Complexity

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

Implementation Notes

• sys.stdin.read is used for faster input.

• The size of the difference array is set to \(N+2\) to prevent out-of-bounds access when referencing \(R_j+1\).

• The final check is done with current % 2 == 1 to count lights that were operated on an odd number of times.

  Source Code

import sys
input = sys.stdin.read

def main():
    data = input().split()
    N = int(data[0])
    M = int(data[1])
    
    # 差分配列を用意
    diff = [0] * (N + 2)
    
    idx = 2
    for _ in range(M):
        L = int(data[idx])
        R = int(data[idx+1])
        idx += 2
        diff[L] += 1
        diff[R + 1] -= 1
    
    # 累積和を計算して各照明の操作回数を求める
    current = 0
    count = 0
    for i in range(1, N + 1):
        current += diff[i]
        if current % 2 == 1:
            count += 1
            
    print(count)

if __name__ == "__main__":
    main()

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