# YNUCPC Contest 2 - E: Minimum Xor Query

[問題へのリンク](https://yukicoder.me/problems/no/3423)

公式解説では Mo's Algorithm を使っていましたが、Mo を使わず通常の平方分割でも解けます。（本質はあまり変わっていないと思いますが）

---

非負整数列 $A$ を $B$ 個の列に分割します。$i (1\leq i \leq \lceil \frac{N}{B} \rceil)$ 番目の列を $C_i = (A_{1},A_{2},...,A_{\min(iB,N)})$ とします。（$i$ 番目の列には $\min(iB,N)$ 番目までの $A$ の prefix が入っているとします）

各 $C_i$ について、非負整数を昇順に並べた時の隣接XORを管理することを考えます。列に対して、追加・削除・最小値クエリに答えられるデータ構造を用意します。これは [ABC308-G](https://atcoder.jp/contests/abc308/tasks/abc308_g) と同様で、列の値の集合を multiset で管理し、隣接XORの最小値を multiset や segtree などで管理すればよいです。全ての $C_i$ に対して隣接XORを管理しても雑計算ですが空間計算量は $O(NB)$、時間計算量は $(NB \log N)$ などになります。

クエリ1を処理するとき、$A_i$ が含まれている全ての $C_j \space(\lfloor \frac{i}{B} \rfloor \leq j \leq \lceil \frac{N}{B} \rceil)$ に対して、$A_i$ を削除して $x$ を追加するということをすればよいです。計算量は $O(\lceil \frac{N}{B} \rceil \log N)$ です。

クエリ2を処理するとき、$k=\lfloor \frac{r}{B} \rfloor$ として、$C_k$ に対して 値 $A_{k*B+1},A_{k*B+2},...,A_{r}$ を追加してクエリに答えればよいです。計算量は $O({B} \log N)$ です。

以上より、$B=\sqrt{N}$ とすればクエリごとに時間計算量 $O(\sqrt{N} \log N)$、前計算（隣接XORを管理するデータ構造の構築）に時間計算量 $O(N\sqrt{N}\log{N})$ でこの問題を解くことが出来ました。

[提出](https://yukicoder.me/submissions/1144181)

実際にACを取るにはバケットサイズガチャや定数倍高速化をかなり頑張らないといけないと思います。(隣接XORを管理するデータ構造の定数倍が重めのため)