나중에 풀 문제

각 태그 목록을 길이 $K$의 비트마스크로 생각하자. 3 S 쿼리는 현재 존재하는 마스크 $T$ 중 $(T \& S)=S$인 것들의 개수를 묻는다.

비트를 왼쪽 절반과 오른쪽 절반으로 나눈다. 왼쪽 절반의 길이를 $L=\lfloor K/2 \rfloor$, 오른쪽 절반의 길이를 $R=K-L$이라 하자.

배열 $F[a][b]$를 다음과 같이 유지한다.

$$F[a][b] = \sum c[a][r]$$

여기서 합은 오른쪽 절반 마스크 $r$이 $b$의 모든 $1$비트를 포함하는 모든 경우에 대해 취하며, $c[a][r]$은 왼쪽 절반이 정확히 $a$이고 오른쪽 절반이 정확히 $r$인 문제의 개수이다.

태그 목록 $(a,r)$을 갖는 문제를 $x$개 추가하거나 제거할 때는 오른쪽 절반에서 $r$의 모든 부분집합 $b$에 대해 $F[a][b]$에 $x$ 또는 $-x$를 더한다. 부분집합의 개수는 최대 $2^R$개이다.

질의 태그 목록이 $(s_L,s_R)$일 때, 왼쪽 절반이 $s_L$의 모든 $1$비트를 포함해야 하고, 오른쪽 절반은 $F$에 이미 누적되어 있다. 따라서 $s_L$을 포함하는 모든 왼쪽 절반 마스크 $a$에 대해 $F[a][s_R]$를 더하면 된다. 이 경우의 개수는 최대 $2^L$개이다.

따라서 각 쿼리는 $O(2^{\lceil K/2 \rceil})$ 시간에 처리된다. 필요한 메모리는 $O(2^K)$이다. 제한에서 $K \leq 24$이므로 충분히 가능하다.

Solution written by GPT5.5