XOR = OR

解説

$P_0=0,\ P_i=A_1\oplus\cdots\oplus A_i$ と定義する。

区間 $[l,r]$ のビット単位 OR を $v$ とすると、この区間が条件を満たすことと

$$P_{l-1}=P_r\oplus v$$

であることは同値である。

区間の右端 $r$ それぞれに対し、左端 $l$ を $r,r-1,\ldots,1$ の順番に考える。区間 $[l,r]$ のビット単位 OR は各ビットが $0$ から $1$ に変化することしかないため、異なる値は高々 $31$ 種類である。また、同じ値を取る $l$ は連続している。

したがって、ビット単位 OR が $v$ となる $l$ の範囲を $[L,R]$ とすると、この範囲で条件を満たす区間の個数は

$$P_{l-1}=P_r\oplus v\qquad (L\le l\le R)$$

を満たす $l$ の個数として求められる。これは、 $(P_i,i)$ の列をソートし二分探索するなどして高速に求めることができる。

区間の右端を $r-1$ から $r$ にすることを考えると、$l\lt r$ に対する区間 $[l,r]$ のビット単位 OR は、区間 $[l,r-1]$ のビット単位 OR に $A_r$ を OR した値になる。

さらに、区間 $[r,r]$ のビット単位 OR は $A_r$ である。これらを求め、同じ値を取る連続した範囲をまとめればよい。

このようにすることで $O(N\log{\max{A}}\log N)$ などでこの問題を解くことができる。