1467. How Many Positions End Up Odd
A row of n lamps is given, indexed from 0, all switched off. Then q
sweeps arrive, each written l r: every lamp from l to r - 1 is TOGGLED.
The range is HALF-OPEN, so lamp r is not touched, and a sweep ending at r
and one starting at r share no lamp.
Print how many lamps are on at the end.
n=6, toggle [0,3), [2,5), [4,6) -> 4
n=5, toggle [0,5), [0,5) -> 0
n=4, toggle [0,2), [2,4) -> 4
Trace the first line. Lamp counts after the three sweeps are
1 1 2 1 2 1, so lamps 0, 1, 3 and 5 are toggled an odd number of times and
are on: four of them.
The third line is the endpoint rule. [0,2) covers lamps 0 and 1 and [2,4)
covers lamps 2 and 3, with no lamp toggled twice, so all four end up on. Read
the ranges as inclusive and lamp 2 would be toggled twice and end up off.
## What most people try first
Toggling each lamp in each range. It is correct and it is O(r - l) per
sweep, so 2 * 10^5 sweeps over the whole row is 4 * 10^10 toggles.
The second reflex is a full difference array of counts, then a running total, then a test for oddness. That is right and does more work than the question needs, because only the PARITY of each count is ever looked at.
## A difference array over one bit
Work modulo 2 throughout. A sweep flips the parity of every lamp in [l, r),
which changes the parity RELATIVE TO THE PREVIOUS LAMP at exactly two places:
d = array of n + 1 zeros
for each sweep l r: d[l] ^= 1; d[r] ^= 1
parity = 0; on = 0
for i in 0 .. n-1:
parity ^= d[i]
on += parity
O(n + q), about 4 * 10^5 steps at the limits, with an array of bits rather
than of counts.
## Why exclusive-or is the right operation
Adding 1 to a count and flipping a bit are the same operation once only
oddness matters, because addition modulo 2 IS exclusive-or. So the entire
difference-array argument survives: d[i] records whether lamp i has a
different parity from lamp i - 1, a sweep changes that relation only at l
and at r, and the running exclusive-or through i is the parity at i.
The saving is not in the asymptotic cost, which is the same either way. It is that nothing can overflow and the array can be a byte per lamp, and more usefully it makes clear that "toggle" problems and "add one" problems are the same problem seen modulo 2.
## The boundary that breaks a careless implementation
d[r] ^= 1, not d[r - 1] ^= 1, because the range is half-open. And r can
equal n, so the array needs n + 1 slots even though slot n is never read.
Note that ^= and not = matters: two sweeps both starting at l cancel
there, and an assignment would lose that.
## Overflow
The answer is at most n = 200000 and every intermediate value is 0 or 1, so
a signed 32 bit integer, limit 2147483647, holds everything with enormous
room to spare. This problem is here partly to show a case where the difference
array needs no 64 bit arithmetic at all, in contrast with problems 1464 and
1466 next to it.
## Related
Problem 707 uses an exclusive-or difference array to decide the fewest length-k flips that make a binary string all ones, where the flips are chosen rather than given. Problem 1464 is the same shape with real values and asks for the peak. This one is deliberately the simplest member of the family: the values have collapsed to one bit.
Constraints - `1 ≤ n ≤ 200000` - `1 ≤ q ≤ 200000` - `0 ≤ l < r ≤ n`, and the range `[l, r)` is half-open so lamp `r` is not toggled - every lamp starts off
Input
The first line contains two integers n and q.
Each of the next q lines contains two integers l and r: toggle every lamp from l to r - 1.
Output
Print one integer alone on its own line: how many lamps are on after every sweep, where a lamp is on exactly when it was toggled an odd number of times. Print no other words.
Hints
Four rungs, in order. The last two open once you have submitted an attempt. A wrong one counts.