Maximize AND

It is enough to quickly test whether there exists an $A_i$ containing every set bit of a mask $S$.

Create a boolean array $can$ of size $2^{20}$. Initially, set $can[A_i]=\mathrm{true}$ for every value appearing in the sequence. Then, for each bit $b=0,1,\cdots,19$ and every mask $S$ whose $b$-th bit is zero, apply

$$can[S] \leftarrow can[S] \lor can[S \mathbin{|} 2^b].$$

After this SOS DP, $can[S]$ is true exactly when there exists an index $i$ such that $A_i$ contains every set bit of $S$, equivalently $$.

To answer a query $X$, start with $ans=0$ and inspect bits from $19$ down to $0$. If the current bit is set in $X$ and $can[an$ is true, add that bit to . Since higher bits are made 1 whenever this remains feasible, the final value is maximum.

For one test case, preprocessing takes $O(N+20\cdot 2^{20})$ time, and all queries take $O(20Q)$ time. The memory usage is $O(2^{20})$.

Proof

After the SOS DP, $can[S]$ is true exactly when one $A_i$ contains all set bits of $S$. Therefore, during a query, if $can[ans\mathrm{\mid }{}^{}$ is true, there exists a single that simultaneously contains every bit already chosen and bit .

Solution written by GPT5.6