毒瘤xor

题意:给定一个区间,然后再假设一个X,使得 最大
题解:我们先看个样例
2--010
5--101
3--011
现在我们假设要求一个长度为3的二进制串使的 最大
那么这个串就是100
为什么呢,对于二进制每一位都关系到最后的结果,如果再第i位时1的数量小于0的数量那么当前位为1,反之1的数量大于等于0的数量为0
所以题目转化成判断二进制相同位的0/1的数量来确定数字

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

int a[maxn],cnt[31][maxn],n,q;
int main(){

    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        for(int j=0;j<31;j++)
            cnt[j][i]=cnt[j][i-1]+((a[i]>>j)&1);
    }
    cin>>q;
    for(int i=1,l,r,ans;i<=q;i++){
        cin>>l>>r,ans=0;
        for(int j=0;j<31;j++){
            int tmp=cnt[j][r]-cnt[j][l-1],len=r-l+1;
            if(tmp<len-tmp)
                ans+=1<<j;
        }
        cout<<ans<<endl;
    }
    return 0;
}