Bug Is Feature (Conditional Version)

Compressing One Game

Start with one game. Write the sorted AP as $A,A+d,A+2d$, where $d>0$.

Now classify moves by which sorted element gets increased.

• Increase the smallest $A$: the other two numbers are $A+d,A+2d$. To stay an AP with common difference at least $d$, the new number must be $A+3d$. So the state becomes $A+d,A+2d,A+3d$.
• Increase the middle $A+d$: the endpoints $A,A+2d$ stay fixed. The old midpoint is useless because the move must increase something, so the only valid AP with non-decreasing difference is $A,A+2d,A+4d$.
• Increase the largest $A+2d$: nope. The two smaller fixed numbers force the third number to be the old largest, or they become endpoints with smaller difference. Neither is a valid positive move. The largest is basically decorative furniture.

So every move is one of only two types:

• shift: $(A,d) -> (A+d,d)$, requiring $A+3d <= x$;
• double: $(A,d) -> (A,2d)$, requiring $A+4d <= x$.

Define

$y = floor((x-A)/d)$.

The initial game always has $y>=2$. The shift move exists when $y>=3$ and sends $y$ to $y-1$. The double move exists when $y>=4$ and sends $y$ to $floor(y/2)$.

So the whole single-game state is just one integer $y$. Nice. The scary three-number game was wearing a fake mustache.

The Grundy Recurrence

Let $g(y)$ be the Grundy value for a game with parameter $y$. Then:

• $g(2)=0$, since no move exists;
• for $y>=3$, there is a move to $y-1$;
• for $y>=4$, there is also a move to $floor(y/2)$.

It is convenient to define a fake helper value $g(1)=2$. Then the recurrence becomes uniform for every $y>=2$:

$g(y)=mex(g(y-1), g(floor(y/2)))$.

That fake $g(1)$ is never a real game. It just makes the algebra stop being annoying.

The recurrence only ever produces $0,1,2$. The closed form is:

• if $v_2(y)$ is odd, then $g(y)=0$;
• otherwise write $y=2^{2s}(2k+1)$. Then $g(y)=2$ if popcount(k) is even, and $g(y)=1$ if popcount(k) is odd.

Here $v_2(y)$ means the exponent of $2$ in $y$.

Why does this work? Induct on $y$.

If $v_2(y)$ is odd, then $y$ is even, $y-1$ is odd, and $y/2$ has even $v_2$. Both target values are nonzero, so the mex is $0$.

If $y=4q$, then $y/2$ has odd $v_2$, so its Grundy value is $0$. Also $y-1=4q-1$ is an odd number whose popcount parity is opposite to the odd core of $q$. Therefore $g(y-1)$ is the opposite nonzero value from $g(q)$, and mex(0, opposite) gives $g(q)$. Multiplying by $4$ does not change the value.

If $y$ is odd, say $y=2m+1$, then the recurrence looks at $2m$ and $m$. Exactly one of those carries the zero case, and the other carries the nonzero value determined by the odd core. Passing from that odd core to $m$ flips popcount parity, so the mex with $0$ gives exactly the claimed value for $2m+1$.

That proves the formula.

Combining Many Games

All games are played as a disjoint sum of impartial games. Therefore Bug wins iff the xor of all Grundy values is nonzero.

For one input row, let $d=b-a$. For a fixed cap $x$:

$y = floor((x-a)/d)$.

As $x$ runs over $[l,r]$, the same $y$ appears for a whole block of length $d$:

$x in [a+yd, a+(y+1)d-1]$.

So for one row, we xor $g(y)$ once for every integer $x$ in the query interval. A value repeated an even number of times cancels. This gives a simple block calculation:

• handle the first partial block directly;
• handle the last partial block directly;
• the middle blocks are full blocks of length $d$;
• if $d$ is even, all full blocks contribute zero;
• if $d$ is odd, the full blocks contribute the prefix xor of $g(y)$ over a consecutive range of $y$.

So we need a fast prefix xor

$P(N)=g(1) xor g(2) xor ... xor g(N)$.

Again, $g(1)=2$ is the fake helper, but all real range queries start at $y>=2$, so using prefix differences is fine.

Fast Prefix Xor

From the closed form, nonzero positions are exactly

$y=4^s(2k+1)$.

For a fixed $s$, all valid $k$ satisfy

$0 <= k <= M$, where $M = floor((floor(N/4^s)-1)/2)$.

For those $k$:

• even popcount contributes value $2$;
• odd popcount contributes value $1$.

Only parities of counts matter, because xor cancels pairs.

Let odd(M) be the parity of the number of integers $k$ in $[0,M]$ with odd popcount.

If $M=2q+1$, the numbers split into pairs $(2u,2u+1)$, and each pair has exactly one odd-popcount number. So

odd(M) = (q+1) mod 2.

If $M=2q`, the first$2q$numbers form$q$such pairs, and the last number$2q$ has popcount parity equal to popcount(q). So

odd(M) = (q mod 2) xor (popcount(q) mod 2).

The even-popcount count parity is just (M+1 mod 2) xor odd(M).

Loop over powers of $4$, toggle xor value $1$ if the odd-popcount count is odd, and toggle xor value $2$ if the even-popcount count is odd.

There are only about $30$ powers of $4$ up to $10^{18}$, so each row is handled in $O(log 10^{18})$ time.

Complexity

For each series we do $O(log 10^{18})$ work. Across all test cases, the total is

$O((sum n) log 10^{18})$,

with $O(1)$ extra memory.