CPSCO2019 Session1 E - Exclusive OR Query

• 問題
• AC

平衡二分木を使って数列を昇順に管理する。C++のsetやJavaのTreeSetと同等なものがあればよいはず。それぞれの数は奇数個あれば1個あるとの同等だし、偶数個あれば存在しないのと同じなので、多重集合である必要はない。各クエリ$(L_i, R_i, X_i)$に対しては次の処理を行う:

1. $L_i$以上$R_i$以下の区間に対して愚直にxorを計算する;
2. $L_i$以上$R_i$以下の区間を削除する;
3. 偶奇を考慮して、必要なら$X_i$を挿入する。

1で間に合うというのが思いつかなくて、遅延更新でなんとかしようと粘ってしまった。¹ 言われてみればならしで${\mathcal O}(N+Q\log N)$しか掛かっていない。平衡二分木の構築を合わせると、全体の計算量は${\mathcal O}((N+Q)\log N)$になる。

---

1. でも、それでもできるはず。データの持ち方がおかしかった。 ↩︎