はじめに
昔の問題ではあるんだけど、自分の解法が公式解説・ユーザ解説とは違ったのでメモ的に残しておく。
問題
考察
Al xor Al+1 xor ... xor Ar = Al + Al+1 + ... + Ar
を満たすケースの個数を数える、という問題である。
一見、lとrを全探索する必要があるように見えるが、bit毎に考えると、
要素を増やしたときに同じbitが立っている場合左辺側は小さくなる、ということが起きる。
0b10 ^ 0b11 = 0b01
0b10 + 0b11 = 0b101
というわけで、あるlを固定して、bitが被る前までrを増やしつつカウントする。
さて、0が含まれないケースを考えてみる。（というかそういう問題だと当初誤読していた）
そもそもbitが被らずにどれくらい要素を増やせるのか、を考えてみると、実はそんなにないことが分かる。
Ai<2**20なので、要素を増やすごとに20bitのどこかは埋まっていく。
したがって、実はlを走査しながらrを(l,l+20]の範囲で動かし、bitが被るかを確認していけばいいので、
O(N*log(max(A))で間に合う。
もちろんこのままだと0が含まれているケースが考慮されていないのでWAになる。（なった）
次に0が含まれるケースを考える。
入力例2のような感じで、0が続くとbitは埋まっていかない。
従って、例えば0が200個続いたとき、20個先までで打ち切ったら答えは合わなくなる。
とすると、結局はrは末尾まで見る必要が出てきてしまう。
なので、この例外的なふるまいをする0の部分について圧縮してみよう。
A = [0 0 0 0 1 0 0 0 0]
を0の個数をマイナスで数えて、
B = [-4 1 -4]
という感じにする。
こうすれば、0がいくら連続しても走査量は増えていかない。
(0 1 0 1 ...みたいなケースに備えて,rの範囲は2倍にしておく）
改めて、lを固定してrを動かすことを考えると、
B[l]が負数の時は、
- 内部での数え上げ
-B[l](-B[l]+1)//2 -
rが増やせる場合に-B[l]の個数分カウントする
r側で負数が出てきた時はその分数えあげればいい。
自分の提出