考察
接頭辞に同じ値が何度現れても集合は変わらないため、各列を値が初めて現れた順だけに圧縮すると、問い合わせは異なる値の個数kごとの集合比較になる。
採用する候補: 初出順列と対称差集合を用いる決定的前計算
棄却する候補: 各問い合わせで二つの接頭辞集合を構築する
問い合わせごとに線形時間を要し、N,Qが2×10^5では間に合わない。
A,Bそれぞれについて初出値の列と各位置のdistinct数を作る。kを増やしながら両初出値を対称差集合へ追加・削除し、空ならequal[k]=trueとして、問い合わせでは二つのdistinct数が等しくequal[k]かを答える。
典型の発動条件
初出圧縮
発動条件: 重複回数を無視した接頭辞集合だけが問われる。
各値の最初の出現だけを並べ、元位置をdistinct数へ写像する。
対称差の逐次維持
発動条件: 同じ段階の二集合へ要素が一つずつ追加される。
追加値をトグルし、対称差が空である段階を前計算する。
問題固有の要素
接頭辞集合は初出の瞬間にしか変化しないため、N個の位置ではなくdistinct数の段階を比較すればよい。
別の問題へ持ち帰る視点: 二つの単調増加集合列の一致は、各段階の対称差を差分更新して判定できる。
正当性
各位置にはその接頭辞までのdistinct数を記録すれば、元の長さが違っても同じ初出段階kへ写せる。 AとBのk番目の新値を対称差集合へ順に反転し、集合が空かどうかを記録すればハッシュ衝突なしで判定できる。 両列で異なる値がk個となる接頭辞集合を一段ずつ更新し、等しいkだけの真偽を全問い合わせで共有できる。
実装上の注意
- 重複値ではdistinct数を増やさず、k=0も一致として用意する。入力値が大きいので値そのものを配列添字にせず集合で管理する。
復習の核
- 同じdistinct数だが要素が異なる例、同じ値が長く重複する例、片側だけ新値が現れる境界を含め、素朴なset比較と照合する。
計算量と制約
時間
平衡set版O(N log N+Q)、初出列の対称差。
空間
O(N)。
制約との対応
公式制約の確認範囲: Time limit: 4 sec; Memory limit: 1024 MiB; Constraints: 1 \leq N,Q \leq 2 \times 10^5; 1 \leq a_i,b_i \leq 10^9; 1 \leq x_i,y_i \leq N; All values in input are integers.
出典