Maximum OR Popcount

Only bits $0\dots30$ matter, because every final value is at most $10^9+10^9<2^{31}$. So the maximum answer is $31$.

That means we can precompute the minimum cost for every possible answer:

$$need[k] = \text{minimum operations needed so the OR has at least } k \text{ set bits}.$$

Then each query budget $b$ asks for the largest $k$ with $need[k]\le b$.

Triggering a missing bit

Suppose bit $j$ is currently absent from the OR. Then every array element has bit $j=0$.

For one element $a_i$, the cheapest increment that makes bit $j$ equal to $1$ is:

$$2^j - (a_i \bmod 2^j).$$

So we choose the element with maximum $a_i \bmod 2^j$. That is the closest element to the next number with bit $j$ set.

After this increment, the chosen element has bit $j=1$, but its lower $j$ bits become zero. That is the annoying part. Carries do not ask permission.

Repairing lower bits

If we trigger a higher bit, we might destroy lower bits that were previously contributing to the OR.

Example with one element:

$$1=(001)_2 \to 2=(010)_2.$$

We gained bit $1$, but lost bit $0$, so the OR popcount did not increase.

Therefore, when we add a new bit $p$, we must repair any lower bits that disappeared. The right order is from high to low: $p,p-1,\dots,0$. If bit $j$ is missing, trigger it greedily using the formula above.

This order matters. If you repair low bits first, a later higher trigger can wipe them out again. That would be impressively pointless.

Why choose the lowest missing bit?

Let $p$ be the lowest bit missing from the current OR. All bits below $p$ are currently present.

To increase the OR popcount by one, some missing bit must be created. Choosing a higher missing bit cannot be better: it costs no less structurally and can damage a larger lower range. Triggering the lowest missing bit creates the smallest possible repair job.

So one optimal growth step is:

1. Find the lowest missing bit $p$.
2. Trigger bit $p$ as cheaply as possible.
3. Scan downward and repair every lower bit that is now missing.

After this, bit $p$ is present, all lower bits are present again, and higher bits were never changed. So the OR popcount increases by exactly $1$.

Precomputation

Start with the original array as cur.

Let

$$s=\operatorname{popcount}(cur_1\ |\ cur_2\ |\dots|\ cur_n).$$

For every $k\le s$, need[k]=0.

For each target answer from $s+1$ to $31$:

• find the lowest missing bit $p$ in the current OR;
• set need[target] = need[target - 1];
• for bit = p down to 0:
  • recompute the current OR;
  • if this bit is already present, skip it;
  • otherwise choose the element with maximum a[i] mod 2^bit;
  • add the needed increment to that element and to the cost.

Then answer each query using upper_bound(need.begin(), need.end(), b).

Complexity

There are only $31$ bits. For each target answer, we scan at most $31$ bits, and each trigger scans all $n$ elements.

So preprocessing costs:

$$O(31^2 n)$$

and each query costs:

$$O(\log 31).$$

Memory is $O(n)$.