基本方針

\(A\) の先頭 \(x_i\) 項に含まれる値の集合を \(S_A\) 、\(B\) の先頭 \(y_i\) 項に含まれる値の集合を \(S_B\) とします。\(|S_A| \neq |S_B|\) の場合、明らかに答えは No です。よって、\(|S_A| \neq |S_B|\) かどうかと、 \(|S_A| = |S_B|\) の場合に \(S_A\) と \(S_B\) が一致するかどうかを高速に判定することで本問を解くことが出来ます。

前計算①

まず、C++におけるsetのようなデータ構造を用意し、 \(S\) とします。\(i=1,2,...,N\) に対して \(a_i\) を\(S\) に挿入して \(S\) のサイズを変数に保存、という処理を行うことで \(A\) の先頭 \(i\) 項に含まれる値の集合のサイズを前計算出来ます。\(B\) についても同様の前計算を行えばクエリに対する \(|S_A|, |S_B|\) の値が分かり、\(|S_A| \neq |S_B|\) かどうかを判定出来ます。先述の通り \(|S_A| \neq |S_B|\) ならば答えは No となるため、あとは \(|S_A|=|S_B|\) の場合の判定が出来れば良いです。

前計算②

前計算①において、 \(S\) に \(i\) 番目に(まだ \(S\) に無い値として)挿入される \(A\) の値を \(a_i'\) とします。 \(B\) についても同様に \(b_i'\) を定めます。 \(k=1,2,...\) に対して \(\{a_1', \ldots, a_k'\}\)と\(\{b_1', \ldots, b_k'\}\) が一致するかどうかが分かれば \(k=|S_A|=|S_B|\) とすることでクエリに答えることが出来ます。
これは、再びsetのようなデータ構造 \(S\) を用意し、\(k=1,2,...\) に対し次のような処理を行えば良いです。

• \(S\) に \(a_k'\) が含まれてないならば \(a_k'\) を挿入し、含まれているならば削除する
• \(S\) に \(b_k'\) が含まれてないならば \(b_k'\) を挿入し、含まれているならば削除する
• \(|S|=0\)ならば \(\{a_1', \ldots, a_k'\}\)と\(\{b_1', \ldots, b_k'\}\) が一致してると判定し、そうでなければ一致していないと判定する

\(S\) に値が含まれていないならば挿入し、含まれているならば削除するという操作をすることにより、各値は \(\{a_1', \ldots, a_k'\}\)と\(\{b_1', \ldots, b_k'\}\) のどちらか一方のみに含まれるならば \(S\) に含まれ、どちらにも含まれる/どちらにも含まれないならば \(S\) に含まれないことになります。よって、\(S\) に含まれる値が存在しないことが \(\{a_1', \ldots, a_k'\}\)と\(\{b_1', \ldots, b_k'\}\) が一致するための必要十分条件となります。
この解法の時間計算量は \(\mathrm{O}(N\log N)\) です。

別解(+Bonus)

本問はZobrist Hashを用いて集合の一致判定を確率的に行うことで解くことも出来ます。
また、セグメント木のような値の更新・区間 \(XOR\) を行えるデータ構造と併せることで次のようなクエリに答えることも出来ます。

• \(a_{x_i}, a_{x_i+1} \ldots, a_{y_i}\) に含まれる値の集合と \(b_{z_i}, b_{z_i+1} \ldots, b_{w_i}\) に含まれる値の集合が等しいかを判定せよ。