Division Versus Addition

Let

$S=\sum_i \lfloor\log_2 b_i\rfloor.$

This is the “division debt” of the current array.

If Poby changes $x$ into $\lfloor x/2\rfloor$, then

$\lfloor\log_2 \lfloor x/2\rfloor\rfloor=\lfloor\log_2 x\rfloor-1.$

So every Poby move decreases $S$ by exactly $1$.

Rekkles changes $x$ into $x+1$. This usually does not change $\lfloor\log_2 x\rfloor$. It increases it by $1$ only when

$x=2^k-1,$

because then $x+1=2^k$.

So if Rekkles makes $B$ useful moves, the final score is

$\text{score}=S_{initial}+B.$

The whole problem is now: how many useful Rekkles moves can happen under optimal play?

Classify each current element $x\ge 2$:

• type $0$: $x$ is a power of two, $x=2^k$;
• type $1$: $x$ is one more than a power of two, $x=2^k+1$;
• type $2$: everything else.

Let $c_1$ be the number of type $1$ elements and $c_2$ the number of type $2$ elements. The key claim is:

$B=c_2+\left\lfloor\frac{c_1}{2}\right\rfloor.$

Yeah, that formula looks a little too clean. But it drops out nicely.

Define

$\Phi=c_2+\left\lfloor\frac{c_1}{2}\right\rfloor.$

We prove that $\Phi$ is exactly the number of future useful Rekkles moves.

First look at Rekkles's move after Poby has moved.

If Rekkles touches a type $2$ element, two things can happen:

• if it was $2^k-1$, he gets one useful move, but the element becomes $2^k$, so $c_2$ drops by $1$;
• otherwise it stays type $2$ and he gets no useful move.

Either way, “immediate useful move plus new $\Phi$” does not increase.

If Rekkles touches a type $0$ element, it becomes type $1$. This increases $\Phi$ exactly when the old $c_1$ was odd.

If Rekkles touches a type $1$ element, it either becomes type $2$, or in the special case $3\to4$ gives an immediate useful move. In both cases, the same parity rule appears: the combined value increases exactly when the old $c_1$ was odd.

So after Poby's move, Rekkles can add exactly

$c_1\bmod 2$

to the future useful-move count.

Now look at Poby.

If Poby divides a type $1$ element, then $c_1$ decreases by $1$, so the parity flips. The decrease in $\Phi$ and the parity bonus available to Rekkles perfectly cancel. Net result: $\Phi$ stays the correct value.

If there is no type $1$, then $c_1$ is even. Poby can divide any available element safely:

• type $0$ stays type $0$;
• type $2$ either stays type $2$, or becomes type $1$, in which case $\Phi$ drops by $1$ but Rekkles gets the parity bonus $+1$.

Again, net result is exactly the old $\Phi$.

So optimal play preserves the claim:

$B=c_2+\left\lfloor\frac{c_1}{2}\right\rfloor.$

Therefore for the original query range $[l,r]$:

$\boxed{\text{answer}=\sum_{i=l}^r \lfloor\log_2 a_i\rfloor + c_2 + \left\lfloor\frac{c_1}{2}\right\rfloor}.$

Where inside the range:

• $c_1$ = count of numbers $a_i$ such that $a_i-1$ is a power of two;
• $c_2$ = count of numbers that are neither powers of two nor one more than a power of two.

Build prefix sums for:

• $\lfloor\log_2 a_i\rfloor$;
• type $1$ count;
• type $2$ count.

Then each query is $O(1)$.

Complexity per test case:

$O(n+q)$

Memory:

$O(n)$