Codeforces Round #340 (Div. 2) E. XOR and Favorite Number

Mo's algorithm を知ってればそこそこ楽に解けるけど、知らないと平方分割力が必要な問題。

Mo's algorithm をして欲しそうな問題に見える。

$ f(i,j) = a_i \oplus a_{i+1} \oplus \cdots \oplus a_{j} $ は $ g(i) = a_1 \oplus a_2 \oplus \cdots \oplus a_i $ を用いて

$$ f(i,j) = g(j) \oplus g(i - 1) $$

と表せる。よって、区間 [L-1, R] の中にある値 g(i) の個数を num という配列で管理することにすると、区間 [L, R] における選び方の総数は

$$\sum_{i<K\oplus i} num[i] \cdot num[K \oplus i]$$

になることがわかる。ただしK=0 のときは式が変わって

$$\sum \frac{num[i] (num[i]-1)}{2}$$

になる。

区間 [L,R] における選び方の総数と num がわかっていれば、[L-1,R], [L+1,R], [L,R-1], [L,R+1] のときの選び方の総数と num は容易に求められるので、Mo's algorithm が使える。

計算量は O((n+m)√n)。

直前に Mo's algorithm の記事を上げてたので歓喜してた。つい最近まで O(N√N) は遅いと思ってたのだけど、よく考えたら O(N log² N) とあまり変わらない。