题解 | #毒瘤xor#

#include<bits/stdc++.h>
#include<iostream>
using namespace std;
int n, q;
int arr[100010];
int arr_cnt[100010][31]={0};
int calc(int l, int r)
{   
    int x[32] = { 0 };
    for (int i = 0; i < 31; i++)
    {
        if (2*(arr_cnt[r][i]-arr_cnt[l-1][i]) >= r - l + 1)
        {
            x[i] = 0;
        }
        else
            x[i] = 1;
    }
    int res = 0;
    for (int i = 30; i >= 0; i--)
    {
        res *= 2;
        res += x[i];
    }
    return res;
}
int main()
{
    cin >> n;
    for (int i = 1; i <=n; i++)
    {
        int j=0;
        cin >> arr[i];
        int y = arr[i];
        while (y != 0)
        {
            if ((y & 1) == 1)
                arr_cnt[i][j]++;
            y >>= 1;
            j++;
        }
    }
    for(int i=2;i<=n+1;i++)
    {
        for(int j=0;j<31;j++)
            arr_cnt[i][j]+=arr_cnt[i-1][j];
    }
    cin >> q;
    int l;
    int r;
    for (int i = 0; i < q; i++)
    {
        cin >> l >> r;
        cout << calc(l, r) << endl;
    }
}

本题重要思想： 1、异或0不变，异或1取反 2、对于每一位单独考虑 3、要使异或后的和最大，应该尽量使每一位异或的结果1的个数多余0的个数，也由此决定了X在各位的值是1还是0。因此要预处理出每一位1的个数。 4、要注意本题时间限制，如果在每次计算时去求每一位1的个数，则会超时。因此最好预处理出序列中每个数在各位的0、1情况，再进行前缀和，这样在calc计算时只需要做个减法便能得出区间内各位1的个数。 5、输出X时可以用pow()函数，但更推荐像本题中从高位不断进行res *= 2；res += x[i];来输出。