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)。
Codeforces Round #340 (Div. 2) E. XOR and Favorite ...
直前に Mo's algorithm の記事を上げてたので歓喜してた。
つい最近まで O(N√N) は遅いと思ってたのだけど、よく考えたら O(N log2 N) とあまり変わらない。