Chef and Easy Problem [CodeChef March Challenge 2018 Div1 B]

https://www.codechef.com/MARCH18A/problems/XXOR

N要素の配列Aがある。
これについて以下のクエリに答える。
「(A[L] xor X) + (A[L+1] xor X) + ... + (A[R] xor X)が最大となるXを答えよ（X＜2^31）」

前提知識

• 累積和
• XORについての知識

解法

https://www.codechef.com/viewsolution/17597909

まずXOR問題によくあることだが、答えはbit毎に独立して考えることができる。
よって、独立して考えることにしよう。
　
答えのd番目のビットが立つ条件を考える。
するとA[L]～A[R]のd番目のビットの0の個数と1の個数を比較したときに0の個数の方が多い時にビットを立ててxorさせるのが良いと言える。
なので、ビット毎に区間の1の個数を素早く応えられるように累積和を作っておこう。

int N, Q, A[101010], sm[31][101010];
//---------------------------------------------------------------------------------------------------
void _main() {
    cin >> N >> Q;
    rep(i, 0, N) cin >> A[i];
    rep(d, 0, 31) {
        rep(i, 0, N) if (A[i] & (1 << d)) sm[d][i] = 1;
        rep(i, 1, N) sm[d][i] += sm[d][i - 1];
    }
 
    rep(q, 0, Q) {
        int L, R; cin >> L >> R;
        L--; R--;
 
        int ans = 0;
        rep(d, 0, 31) {
            int one = sm[d][R];
            if (L) one -= sm[d][L - 1];
 
            int zero = R - L + 1 - one;
 
            if (one < zero) ans += (1 << d);
        }
        printf("%d\n", ans);
    }
}