毒瘤xor

毒瘤xor

解题思路
用前缀和预处理31位二进制数每一位1的个数，区间[L, R]上每一位如果1的个数多于0的个数，X对应二进制位上值为0，否则为1
注意若有多组可行解，需要输出较小的解，则当0和1个数一样时，X对应二进制位上取0

AC代码

#include <iostream>

using namespace std;
const int N=100010;
int n,q;
int l,r;
int a[N][35];
int sum[N][35];

int main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i][0];
        for(int j=1;j<=31;j++)
        {
            a[i][j]=a[i][0]>>(j-1)&1;
        }
    }
    for(int i=1;i<=n;i++)  //求前缀和
    {
        for(int j=1;j<=31;j++)
        {
            sum[i][j]+=a[i][j]+sum[i-1][j];
        }
    }
    cin>>q;
    while(q--)
    {
        int x=0;
        int cnt;
        cin>>l>>r;
        for(int i=1;i<=31;i++)
        {
            cnt=sum[r][i]-sum[l-1][i];
            if(cnt<r-l+1-cnt)
                x+=1<<(i-1);
        }
        cout<<x<<endl;
    }

    return 0;
}