区間$I$に関する$f$の値は、$(A_i)_{i \in I}$中のhighest set bitの位置を$k$として、$k$が立っている数が$(A_i)_{i \in I}$に何個含まれるかでだいたい決まる:
- $k$が立っている数が1個でそれ以外が0個の場合、その数自身になる
- $k$が立っている数が奇数個の場合、上の場合を除いて$2^k$になる
- $k$が立っている数が2個でそれ以外が0個の場合、不定
- $k$が立っている数が2個でそれ以外が1個の場合、不定
- $k$が立っている数が2個でそれ以外が2個以上の場合、0にできる
- $k$が立っている数が4個でそれ以外が$0$個の場合、不定
- $k$が立っている数が4個でそれ以外が$1$個以上の場合、0にできる
- $k$が立っている数が6個以上の偶数の場合、それ以外が何個でも0にできる
まずは、$k$が立っている数が偶数個の時に常は$f$の値が0になり、$k$が立っている数が奇数個の時は常に$2^k$になるとして、偶奇のみに注目して計算する。そして、後から3, 4, 6のパターンを別に数えて補正する。
前半パートは、$i = 1, 2, ..., N$についてそれぞれ区間$[1, i], [2, i], ..., [i, i]$に関する結果の和を求めるとよい。この際、
- $\operatorname{odd}[x] :=$ highest set bitが$x$で、$x$が立っている数を奇数個含むような区間の数
- $\operatorname{even}[x] :=$ highest set bitが$x$で、$x$が立っている数を偶数個含むような区間の数
を保持しながら走査するとまとめて計算できる。${O}(N\log \max A_i)$。
