コンテスト中AC:A〜D
Eはコンテスト後に解説を読み、自分がコンテスト中に考えていた発想で問題なさそうだったので、その方針でなんとかACできました。
E問題について書いたので、記事のタイトルはEをメインにしました。

E - Prefix Equality
- 自分の実装
- Zobrist Hash

E - Prefix Equality

自分の実装

こちらの解説と多分同じ考え方だと思います。(多分)

方針

大雑把なイメージです。
$(a_1,...,a_i)$ から得られる集合を $S^a_i$ とします。同様に、 $(b_1,...,b_j)$ から得られる集合を $S^b_i$ とします。

$S^a_i$ と等しい $S^b_j$ が存在すると仮定し、その中で最小の $j$ を $l$ とします。

$j=l,l+1,...$ と増加させ、 $b_j$ を追加していくと、そのうち集合として等しくなくなります(但し、便宜上 $b_{N+1}$ に $A$ に含まれない値があるものとします。)。この時の $j$ を $r$ とします。

この時、 $S^a_i$ に対しては、 $l\leq j\lt r$ を満たす $S^b_j$ が全て等しくなります。

よって、各 $i$ について、 $j$ の区間を前計算しておけば、各クエリに $O(1)$ で答えられます。

前計算の計算量

愚直に各 $i$ について、 $j$ の区間を求めようとすると、少なくとも $O(N^2)$ くらいにはなってしまいます。

しかし、実は $i=1,2,..$ と探索していくと、 $j$ の探索範囲も増加するだけになり、結果として $O(N)$ くらいになります。
具体例と共になぜそうなるか書いていきたいと思います。

前計算の処理

以下の数列を例にします。
$A=\{1,2,1,5,2,3\}$
$B=\{2,1,2,1,3,5,-1\}$ (-1は番兵)

以下の集合を定義します。

$S_A$ : $S^a_i$ に含まれ、 $S^b_{j-1}$ ではまだ見つかっていない値の集合
$S_{AB}$ : $S^a_i$ と $S^b_{j-1}$ に共通して存在する値の集合

$i=1,2,...,N$ について、 $A$ の先頭 $i$ 項と $B$ の先頭 $j$ 項が等しくなるような $j$ の区間を求めます。
初め $j=1$ としておきます。

(1) $S_A$ に $a_1=1$ を追加し、これに対応する $j$ の区間を求めます。
$b_1 = 2$ であり、 $S_A$ に一致する値がないので、これに一致する $j$ の区間は存在しません。

(2) $S_A$ に $a_2$ を追加します。 $S_A=\{1,2\}$ です。
$b_1 = 2$ なので、 $S_A$ から $2$ を削除して、 $S_{AB}$ に追加します。 $b_2=1$ も同様です。

ここで、 $S_A$ が空になりました。これは、 $S^a_2 = S^b_2$ となったことを指します。よって、 $i=2$ のときに集合が等しくなる時の下限は $j=2$ です。下限が見つかったため、上限を調べます。

現在、 $S_{AB}=\{1,2\}$ です。
$b_3=2,\ b_4=1$ は $S_{AB}$ に含まれるので、 $S^a_2 = S^b_2 = S^b_3 = S^b_4$ となります。
次の $b_5 = 3$ は $S_{AB}$ に含まれないので、この時点で、 $S^a_2 \neq S^b_5$ となります。従って、半開区間 $[2,5)$ が $i=2$ の時に集合として等しくなる $j$ の区間です。

(3) $a_3=1$ は $S_{AB}$ に含まれ、更に $S_A$ が空です。よって、 $S^a_3$ は一個前の $S^a_2$ と等しく、かつ、 $S^a_2$ には $j$ の区間が存在していることがわかります。

この場合、 $S^a_3 = S^a_2$ であることから、 $i=3$ についての $j$ の区間は $i=2$ の時と同じになります。

(4) $a_4=5$ を $S_A$ に追加します。この時、新たに $j$ の区間を再探索しますが、 $j=5$ からの探索として良いです。
なぜなら、 $b_1,b_2,b_3,b_4$ は $a_1,a_2,a_3$ に含まれるため、 $S^a_4$ を集合として等しくするために必要になるからです。また、 $b_5$ は $a_1,a_2,a_3$ に含まれない最初の値なので、ここから探索を開始する必要があります。

$j$ の区間の探索をしますが、 $b_5=3$ で、これは $S_A$ に含まれません。よって、 $i=4$ と等しい $j$ の区間は存在しません。

(5) $a_5=2$ は $S_{AB}$ に存在するので、既に $S^a_4,S^b_4$ の両方に共通して存在しています。そのため、 $S_A$ には追加しません。
$j$ の区間の探索をしますが、 $b_5=3$ で、これは $S_A$ に含まれません。よって、 $i=5$ と等しい $j$ の区間は存在しません。

(6) $a_6=3$ を $S_A$ に追加し、 $S_A=\{3,5\}$ となります。

$j$ の区間を探索すると、 $b_5 =3,\ b_6=5$ と進めると、両方 $S_A$ に含まれるので、 $S_A$ から削除し、 $S_{AB}$ に追加します。 $j=6$ の時点で $S_A$ が空になったので、 $j=6$ が、 $S^a_6$ と等しくなる下限です。
上限ですが、番兵として入れてある $b_7=-1$ が $S_{AB}$ に含まれないので、 $i=6$ の時は、 $[6,7)$ が該当の区間になります。

以上で、全ての $i$ に対する $j$ の区間が求まりました。

例で示したように、 $j$ は常に、 $A$ の $i$ 項目までに含まれない最初の値を指すようにしておきます。
すると、 $i+1$ 目項までと等しい区間を探す際に $j$ から開始すればよくなります。
なぜなら、 $S^a_{i+1}$ と等しい区間を探す際に、 $S^a_{i+1}$ は $S^a_{i}$ を部分集合として含むため、少なくとも $S^a_{i}$ と共通な値のみを含む $S^b_{j-1}$ が必要となるからです。
これで、 $j$ は増加させるだけでよいことがわかりました。