题解 | #毒瘤xor#

思路

可以用位运算和前缀和的相关知识。
要让X异或a[i]求和最大SUM，则SUM的每一位都是1，我们需要求的是X的每一位该取0还是1。
我们可以用一个二维数组a[i][j]记录前i个数第j位是1的个数，这样我们就能知道L~R范围内某一位的0多还是1多。
运用异或的性质我们知道，在0多的情况下X那一位该取1，在1多的情况下X那一位该取0；
而0和1一样多的时候，根据题意X尽可能小，就取0。

代码

#include<bits/stdc++.h>
using namespace std;

int n,q,a,l,r;
int sm1[100005][32];
//sm[i][j]:第i个数前面第j位有多少个0/1;

int main(){
    scanf("%d",&n);
    memset(sm1,0,sizeof(sm1));
    for(int i=1;i<=n;i++){
        scanf("%d",&a);
        int j=0;
        while(a){
            if(a&1) sm1[i][j]++;
            a>>=1;
            j++;
        }
        for(int j=0;j<=30;j++){ //求前缀和 
            sm1[i][j]+=sm1[i-1][j];
        }
    }
    scanf("%d",&q);
    for(int i=1;i<=q;i++){
        scanf("%d%d",&l,&r);
        int ans=0,len=r-l+1;
        for(int j=0;j<=30;j++){
            if(2*(sm1[r][j]-sm1[l-1][j])<len)
        //l到r在j位上0的个数之和比1多，那么X的j位是1 
                ans+=(1<<j); // 
        }
        cout<<ans<<endl;
    }
    return 0;
}