CodeChef October Challenge 2020 - Compress all Subsegments

• 問題
• AC

区間$I$に関する$f$の値は、$(A_i)_{i \in I}$中のhighest set bitの位置を$k$として、$k$が立っている数が$(A_i)_{i \in I}$に何個含まれるかでだいたい決まる:

1. $k$が立っている数が1個でそれ以外が0個の場合、その数自身になる
2. $k$が立っている数が奇数個の場合、上の場合を除いて$2^k$になる
3. $k$が立っている数が2個でそれ以外が0個の場合、不定
4. $k$が立っている数が2個でそれ以外が1個の場合、不定
5. $k$が立っている数が2個でそれ以外が2個以上の場合、0にできる
6. $k$が立っている数が4個でそれ以外が$0$個の場合、不定
7. $k$が立っている数が4個でそれ以外が$1$個以上の場合、0にできる
8. $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)$。