$A,B$ に使われている数値を、 $A$ での登場順に $0, 1, 2, \cdots$ となるよう、 数値を振り直します。 $B$ にしか登場しない数値は、 $A$ で使った数値より大きな数値を適当に振ります。

すると、 $A$ の各集合は、 種類数 $k$ の時 $\{0, 1, \cdots, k-1\}$ になります。 $B$ の各集合との一致を「種類数と最大値の一致」のみで判定可能になり、簡便です。

あらかじめ $i=1, \cdots, N$ に対し、

• $A$ の先頭 $i$ 項による集合の種類数
• $B$ の先頭 $i$ 項による集合の種類数と最大値

を求めておけば、各クエリに $O(1)$ で答えられます。

計算量は、数値の振り直しや種類数のカウントにC++のmapやsetを使うと $O(N\log N+Q)$ 、unordered_mapなどのハッシュを使うと $O(N+Q)$ です。