ハッシュを用いることで、小さい確率で失敗することを許す代わりに \(O(N+Q)\) で簡単に判定できます。

整数 \(a\) のハッシュを適当に定めます。また集合のハッシュを、それが含む整数たちのハッシュの和と定義します。 前計算で \(A, B\) のそれぞれについて先頭から第 \(i\) 項まで（\(i=1, \cdots, N\)）がなす集合のハッシュを \(O(N)\) で求めておくと、各クエリを \(O(1)\) で判定できます。

こちらの AC コード（PyPy3） では、整数 \(a\) のハッシュを \(a * (a + 1346) * (a + 9185)\) としています。