Bitwise And Equals

Let $U=2^{20}$. All initial values and all queries are below $U$.

We will solve every query $X$ independently, but we need preprocessing good enough for $2\cdot 10^5$ queries. The trick is to stop thinking about individual increments one by one. Carries are the whole game here.

Step 1: force the 1 bits of $X$

For a fixed $X$, every final value must contain all bits of $X$. For each $a_i$, define

$m_i=\min\{y\ge a_i:(y\&X)=X\}.$

The cost $m_i-a_i$ is unavoidable in any valid solution, because every valid final value for this element must contain $X$. So first compute the base cost

$C(X)=\sum_i (m_i-a_i).$

How do we compute this fast?

For one number $a$, suppose the highest bit of $X$ that is missing in $a$ is $k$. Then all required bits above $k$ are already fine. The cheapest fix is:

• keep bits above $k$ unchanged,
• set bit $k$ to $1$,
• set lower bits to the lower bits of $X$.

So the increment is

$2^k-(a\bmod 2^k)+(X\bmod 2^k).$

Now group all numbers whose highest missing required bit is $k$. If $H$ is the mask of required bits of $X$ above $k$, then this group is exactly:

• contains all bits of $H$,
• has bit $k=0$.

Precompute

$cnt[M]=\#\{i:(a_i\&M)=M\}$

with SOS DP over supersets. Then the group size is

$cnt[H]-cnt[H\cup\{k\}].$

We also need the sum of $a_i\bmod 2^k$ over that group. Instead of storing 20 big sum arrays, decompose it by bits:

$\sum(a_i\bmod 2^k)=\sum_{r<k}2^r\cdot\#\{\text{group elements with bit }r=1\}.$

That count is

$cnt[H\cup\{r\}]-cnt[H\cup\{k\}\cup\{r\}].$

That gives $C(X)$ in about $O(\sum_{k\in X} k)$ time. Tiny.

Step 2: exact AND, not just superset

After replacing every $a_i$ by $m_i$, all values contain $X$. Let

$A=m_1\&m_2\&\cdots\&m_n.$

If $A=X$, the base cost is already the answer.

Otherwise there is at least one unwanted common bit. Let $g$ be the highest bit such that $A$ has $1$ and $X$ has $0$. This bit is common to every $m_i$, so some element must be increased until bit $g$ becomes $0$.

Here is the important carry fact: to turn bit $g$ from $1$ to $0$ by increasing a number, you must carry into some bit $t>g$ where that number currently has $0$; or into bit $20$.

When we carry into bit $t$, the cheapest possible new lower part is exactly $X\bmod 2^t$. So for a selected temporary value $m_i$ with bit $t=0$, the extra cost is

$2^t+(X\bmod 2^t)-(m_i\bmod 2^t).$

This clears all unwanted common bits below $t$, including bit $g$. Bits above $t$ do not change.

But there is one annoying gotcha, because of course there is. If $t<20$ and the selected element was the only temporary value with bit $t=0$, then after setting its bit $t$ to $1$, bit $t$ becomes common to all values. That would make the AND too large. So a carry into $t$ is valid only when at least two temporary values have bit $t=0$.

Carrying into bit $20$ is always allowed: all other temporary values are still below $2^{20}$, so bit $20$ is not common.

So the extra cost is the minimum over valid $t$:

• for $g<t<20$, if at least two $m_i$ have bit $t=0$, use the largest possible $m_i\bmod 2^t$ among those values;
• for $t=20$, use $U+X-\max_i m_i$.

Step 3: count zeros of temporary values

For a bit $t$ with $X_t=0$, when does $m_i$ have bit $t=1$?

Exactly when:

• $a_i$ already contains every required bit of $X$ above $t$, and
• $a_i$ has bit $t=1$.

If $a_i$ misses a required higher bit, the fix carries above $t$ and resets bit $t$ to $X_t=0$.

Let $H_t$ be the mask of bits of $X$ strictly above $t$. Then

$\#\{i:m_{i,t}=1\}=cnt[H_t\cup\{t\}],$

so

$Z_t=\#\{i:m_{i,t}=0\}=n-cnt[H_t\cup\{t\}].$

The highest unwanted common bit $g$ is the highest $t\notin X$ with $Z_t=0$.

Step 4: maximize the lower part among zero-bit candidates

For a valid carry bit $t$, we need

$\max\{m_i\bmod 2^t:m_{i,t}=0\}.$

There are two ways $m_{i,t}=0$ happens:

1. $a_i$ misses some required bit above $t$. Then the carry happened above $t$, and

$m_i\bmod 2^t=X\bmod 2^t.$

2. $a_i$ contains all required bits above $t$ and has bit $t=0$. Then

$m_i\bmod 2^t=next(a_i\bmod 2^t, X\bmod 2^t),$

where next means the smallest number not below the first argument that contains the second mask.

next is monotone, so for case 2 we only need the maximum lower part $a_i\bmod 2^t$ among numbers with:

• bit $t=0$,
• high part containing $H_t$.

Precompute this with another SOS DP, this time taking maximums over high masks for each bit $t$.

That is the whole thing. The implementation looks scary only because the masks are doing accounting for us; the idea is just “base force $X$, then one carry fixes the highest extra bit.” Carries are rude, but at least they are predictable rude.

Complexity

Preprocessing is $O(20\cdot 2^{20}+20n)$.

Each query costs about $O(20^2)$ in the worst case, with small constants.

Memory is $O(2^{20})$.