Zobrist Hashを用いた解法を説明します。

Zobrist Hashとは、各数に適当な値を割り当てることで、集合の一致判定をする手法です。

各値 \(x\) について、ハッシュ値 \(h_x\) を割り当てます。 この時、区間 \([l, r)\) のハッシュ値は \(\bigoplus_{i=l}^{r-1} h_{S_i}\) として定義されます（ここで \(\bigoplus\) はxorです）。

この時、このハッシュについて以下の性質が分かります。

• 同じ値が偶数回出現した時、そのハッシュ値は0である
• \(h_i\) が大きな値の範囲から無作為に選ばれている時、奇数回出現する値が存在するならば高い確率で非0である

従って、 \(h_i\) をランダムに生成した時、高い確率で区間のハッシュ値が0であるようなものを数え上げる問題になっていることが分かります。

この問題は区間のxor累積和を取ると、xorが同じ場所の個数を数え上げる問題になっているので \(O(N)\) で解くことができます。

なお、今回の制約下では \(h_i = 2^i\) と定めることで決定的に解くこともできます。

余談

偶数回ではなく \(k\) の倍数回出現するかを判定することもできます。

\(h_{i, j}\) を左から見て値 \(i\) が \(j \pmod k\) 回目に出現した時のハッシュ値とし、 \(h_{i, 0} = \bigoplus_{j=1}^{k-1} h_{i, j}\) と定義します。

この時、同じ値を連続で \(k\) 個含むとハッシュ値が0になっていることが確認できます。