Overview

After performing \(M\) operations that “toggle (switch ON/OFF)” the lights in the interval \([L_j, R_j]\), find the number of lights that are ultimately turned on.

Analysis

Each operation toggles all elements within an interval, so naively “toggling each element one by one in the interval” would be close to \(O(NM)\) in the worst case (e.g., toggling long intervals many times), which is definitely too slow for \(N \le 10^6, M \le 2\times10^5\).

The key observations are the following two points:

• Whether light \(i\) is ultimately turned on depends only on the parity of the number of times it was toggled
  • Even number of toggles → unchanged (OFF)
  • Odd number of toggles → toggled to ON
• Range addition (here, “counting the number of range toggles”) can be processed efficiently using a difference array (the so-called imos method) In this problem, we don’t need to count the exact number of times — we only need the parity, so instead of addition, we can manage it using XOR (\(\oplus\)) of \(0/1\).

Concrete example: - Suppose \(N=5\) and the operations are \([2,4]\) and \([3,5]\). - The toggle count (parity) for each position is: 1: 0 times, 2: 1 time, 3: 2 times, 4: 2 times, 5: 1 time - Only positions 2 and 5, which were toggled an odd number of times, are ultimately ON → the answer is 2

By constructing this “parity prefix” using a difference array, we can solve the entire problem in \(O(N+M)\).

Algorithm

Prepare a difference array diff, and represent the range toggle \([L, R]\) with the following updates:

• Toggle diff[L] (diff[L] ^= 1)
• Toggle diff[R+1] (diff[R+1] ^= 1)

Then, take the cumulative XOR from left to right, and count how many positions are ultimately turned on (i.e., have a cumulative value of 1).

• cur = cumulative value (parity) up to the current position
• For each \(i=1..N\):
  • cur ^= diff[i] (parity of the number of toggles up to this point)
  • If cur == 1, then light \(i\) is ON → add to the count

Why this correctly represents range toggles: - diff[L] means “start switching the toggle state from here” - diff[R+1] means “revert the toggle state back here” - When taking the cumulative XOR, cur is in the toggled state only between \(L\) and \(R\)

Complexity

• Time complexity: \(O(N + M)\) (\(M\) difference updates, followed by a single scan over \(1..N\))
• Space complexity: \(O(N)\) (the difference array diff has length approximately \(N\))

Implementation Notes

• Since we only need to know the parity of toggles, using a bytearray (0/1) for the difference array is sufficient (good memory efficiency).

• Since we access R+1, the array should be allocated with a length of at least N+2 (the code uses N+3).

• Since the input is large, we use sys.stdin.buffer.read() to read everything at once and parse integers quickly (this is an important optimization in Python).

  Source Code

import sys

def ints():
    data = sys.stdin.buffer.read()
    n = len(data)
    i = 0
    while i < n:
        while i < n and data[i] <= 32:
            i += 1
        if i >= n:
            break
        sign = 1
        if data[i] == 45:  # '-'
            sign = -1
            i += 1
        x = 0
        while i < n and data[i] > 32:
            x = x * 10 + (data[i] - 48)
            i += 1
        yield sign * x

it = ints()
N = next(it)
M = next(it)

diff = bytearray(N + 3)
for _ in range(M):
    L = next(it)
    R = next(it)
    diff[L] ^= 1
    diff[R + 1] ^= 1

cur = 0
cnt = 0
for i in range(1, N + 1):
    cur ^= diff[i]
    cnt += cur

sys.stdout.write(str(cnt))

---

This editorial was generated by gpt-5.2-high.