CPSCO2019 Session3：E - Enumerate Xor Sum
問題
解法
各 k ごとに考える．
A_1 ~ A_k までの XOR は累積和的に計算できる．この XOR を bit の桁ごとに見ていく．XOR の i bit 目が 1 のとき，A_1 ~ A_k それぞれの i bit 目が反転される．よって，A_1 ~ A_k それぞれの i bit 目が 1 である個数を cnt_i とすると，答えに 2^i * (k - cnt_i) が加算される．また，XOR の i bit 目が 0 のとき，A_1 ~ A_k それぞれの i bit 目はそのままになる．よって，答えに 2^i * cnt_i が加算される．これを各 i について計算すれば各 k について答えが求まる．cnt も累積和的に計算することが出来るので，全体で O(N * logA_max)．
解答
