ABC250 E - Prefix Equality (500)
そのときの個数を先に調べておくことで個数が違う場合を高速に判定できる
$ A,Bについて前から$ i個目まで見たときの要素数を事前に求める
Setを使って前から見ていくと$ \mathcal{O}(N \log N)
個数が同じ場合に対してもその場合の同じ集合かを事前に求めておけば高速に判定できる
$ A,Bの$ i番目までが同じ要素かどうかはSetを使って求める
既にある場合は要素を消して、無い場合は要素を追加
$ A,B両方で処理した後でSetが空なら全要素が偶数個=同じ
Setを使って前から見ていくと$ \mathcal{O}(N \log N)
それぞれのクエリについて要素数が同じかつその要素数の時に同じ集合かどうかを出力
全体で$ \mathcal{O}(N \log N + Q)