【每日一题】毒瘤xor

题目

有 个数 ，给出 个询问，每次询问给出区间 ，现在请找到一个数 ，使得

1. 
2. 最大， 表示异或操作。

解题思路

要使条件 2 成立，需要求出区间 中，所有数值的二进制表示的 31 位，每位 1 的个数。
如果某位 0 的个数大于 1 的个数，那么所求 在该位上取 1，否则取 0。

计算区间 中每位 1 的个数，可以使用前缀和来实现。
区间 中所有数值的第 位中 1 的个数为 。

C++代码

#include<cstdio>
#include<vector>
using namespace std;

int main(){
    int N, q;
    scanf("%d", &N);
    vector<vector<int>> bits(N+1, vector<int>(31,0));
    int a;
    for(int i=1; i<=N; ++i){
        scanf("%d", &a);
        int k = 0;
        for(int k=0; k<31; ++k){
            if((a&1))
                bits[i][k] = bits[i-1][k] + 1;
            else
                bits[i][k] = bits[i-1][k];
            a >>= 1;
        }
    }
    scanf("%d", &q);
    int L, R;
    while(q--){
        scanf("%d%d", &L, &R);
        int X = 0;
        int m = R-L+1;
        for(int i=0; i<31; ++i){
            int k = bits[R][i] - bits[L-1][i];
            if(k < m-k){
                X |= (1<<i);
            }
        }
        printf("%d\n", X);
    }
    return 0;
}