\(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)\) です。