AND 최대화

$S$의 모든 1인 비트가 어떤 $A_i$에도 모두 포함되는지를 빠르게 판정할 수 있으면 된다.

크기 $2^{20}$의 불 배열 $can$을 만든다. 처음에는 등장한 값에 대해 $can[A_i]=\mathrm{true}$로 둔다. 그 다음 각 비트 $b=0,1,\cdots,19$에 대해, $b$번 비트가 0인 모든 마스크 $S$에 다음 전이를 적용한다.

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

이 SOS DP가 끝나면 $can[S]$는 어떤 $A_i$가 $S$의 모든 1인 비트를 포함할 때, 즉 $(A_i \mathbin{\&} S)=S$인 가 존재할 때 정확히 참이다.

이제 쿼리 $X$를 처리한다. 답을 $ans=0$으로 시작하고 비트 $19$부터 $0$까지 내려간다. 현재 비트가 $X$에서 1이고 $can[ans\mathrm{\mid }$가 참이라면 그 비트를 에 추가한다. 높은 비트부터 가능한 한 1로 만들었으므로 마지막 가 최댓값이다.

한 테스트 케이스의 전처리는 $O(N+20\cdot 2^{20})$, 모든 쿼리는 $O(20Q)$에 처리된다. 메모리 사용량은 $O(2^{20})$이다.

증명

SOS DP 이후 $can[S]$가 참이라는 것은 정확히 $S$의 모든 1인 비트를 포함하는 $A_i$가 하나 이상 존재한다는 뜻이다. 따라서 쿼리 처리 중 $can[ans\mathrm{\mid }{2}^b$가 참이면, 지금까지 선택한 모든 비트와 번 비트를 동시에 포함하는 하나의 가 존재한다.

Solution written by GPT5.6