Educational Codeforces Round 12 E. Beautiful Subarrays

数列 A が与えられる。連続する部分列のうち全体を xor したものが K 以上であるようなもの個数を数えよ。

A[L..R] を xor したものを S[L..R] と書くことにすると S[L..R] = S[1..R] xor S[1..L-1] が成り立つ。

ここで S[1..L] を S[L] と再定義すれば、この問題は S[i] xor S[j]≧K となる (i,j) の個数を数える問題になる。

さて S[i] xor S[j]≧K を高速に判定するにはどうすればいいだろうか。i を固定して考えてみよう。

K=000011101110, Si=000101001010 を例に挙げる。

Sj が 1... の形なら確実に K 以上になる。

K=  000011101110
Si= 000101001010
Sj= 1...........

Sj が 01... の形なら確実に K 以上になる。

K=  000011101110
Si= 000101001010
Sj= 01..........

Sj が 001... の形なら確実に K 以上になる。

K=  000011101110
Si= 000101001010
Sj= 001.........

Sj が 0000... の形なら確実に K 以上になる。

K=  000011101110
Si= 000101001010
Sj= 0000........

Sj が 00010... の形なら確実に K 未満になる。

K=  000011101110
Si= 000101001010
Sj= 00010.......

Sj が 000111... の形なら確実に K 未満になる。

K=  000011101110
Si= 000101001010
Sj= 000111......

この作業を見ればわかるように、K 以上（未満）が確定したら探索を中止するようにすれば探索ノード数が高々 30 個程度になる。

接頭辞が s であるようなビット列の個数を管理するのは Trie 木が使える。

上から見ていけば大小比較ができることには気がついていたが、xor を二回取ると 0 になるという基本的なことに気付けなかった。