Overview

Given \(N\) lights, this problem asks you to find the number of lights that are on after performing \(M\) interval switch operations.

Analysis

Each light’s on/off state is toggled by multiple operations. A naive approach that checks the effect of \(M\) operations on each light takes \(O(NM)\) time, which is too slow given the constraints (\(N \leq 10^6\), \(M \leq 2 \times 10^5\)).

Instead, we need a way to efficiently process interval operations. Whether each light is on or off is determined by the parity of the number of operations applied to it (even means off, odd means on). Therefore, we manage the changes in operation counts at each position as events and efficiently compute the result using a sweep line approach.

Algorithm

1. Create events: For each operation \([L_j, R_j]\), create an event of +1 at position \(L_j\) and an event of -1 at position \(R_j+1\).
2. Sort events: Sort the events by position.
3. Sweep line: Sweep from left to right while tracking the current operation count (current). Since the operation count is constant between consecutive events, compute the number of lights that are on from the interval length and the parity of the operation count.
4. Compute the result: Process the interval from the last event to the end in the same manner, and compute the total number of lights that are on.

Complexity

• Time complexity: \(O(M \log M)\)
  • Sorting the events is the dominant factor, sorting \(2M\) events
• Space complexity: \(O(M)\)
  • Memory is used to store the events

Implementation Notes

• Events are managed as tuples of (position, change amount)

• Be careful with endpoint handling (use \(R_j+1\) as the end point)

• Don’t forget to process the interval after the last event

• Check the parity of the current operation count to compute the number of lit lights

  Source Code

def main():
    import sys
    input = sys.stdin.read
    data = input().split()
    idx = 0
    N = int(data[idx])
    idx += 1
    M = int(data[idx])
    idx += 1
    
    events = []
    for i in range(M):
        L = int(data[idx])
        R = int(data[idx + 1])
        idx += 2
        events.append((L, 1))
        events.append((R + 1, -1))
    
    events.sort()
    count = 0
    current = 0
    prev = 1
    total_on = 0
    
    for event in events:
        pos, typ = event
        if pos > prev:
            segment_length = pos - prev
            if current % 2 == 1:
                total_on += segment_length
        current += typ
        prev = pos
        
    if prev <= N:
        segment_length = N - prev + 1
        if current % 2 == 1:
            total_on += segment_length
            
    print(total_on)

if __name__ == "__main__":
    main()

This editorial was generated by deepseekv3.