题解 | #毒瘤xor#

题目考点：前缀和、位运算

题目大意：找到一个数X，使得X和数列区间内所有数字异或后，得到的值最大。

题目分析：暴力解法O(d * 2e10)，其中d为区间长度、2e10为int正整数范围，用派蒙的脑子想想就知道不可取吧？换个想法来看，统计一下区间内的数字的第i位0的个数和1的个数：

若第i位1的个数大于0的个数，X的第i位应当是0
若第i位1的个数小于0的个数，X的第i位应当是1
若第i位1的个数等于0的个数，X的第i位应当是0（题目中说若有多个解，输出较小者）

例如题目中的第一次询问2 5：

位数: 10-31 9 8 7 6 5 4 3 2 1  
78:     0   0 0 1 0 0 1 1 1 0
12:     0   0 0 0 0 0 1 1 0 0
1 :     0   0 0 0 0 0 0 0 0 1
3 :     0   0 0 0 0 0 0 0 1 1
其中1-4位都是0的个数等于1的个数，因此X的1-4位都是0,5-31位都是0比1多，因此5-31位都是1
因此得到111 1111 1111 1111 1111 1111 1111 0000（即2147483632）

而区间查询次数较多，所以用前缀和来维护前i个数每一位1的个数即可：

代码：

#include<iostream>
#include<cstring>
#include<algorithm>

using namespace std;

const int INF = 0x3f3f3f3f;
const int N = 1e5+10;

int n, t, a[N][35];  // a[i][j]表示前i个数字第j位一共有几个1

int main()
{
    scanf("%d", &n);
    for(int i = 1; i <= n; i++)
    {
        int x;
        scanf("%d", &x);
        for(int j = 0; j < 31; j ++)
        {
            a[i][j] = (a[i-1][j] + (x&1));  // 前缀和维护1的个数
            x >>= 1;
        }
    }

    scanf("%d", &t);
    while(t--)
    {
        int l, r, ans = 0;
        scanf("%d%d", &l, &r);
        for(int i = 0; i < 31; i++)
            if((a[r][i]-a[l-1][i])*2 < r-l+1) // 利用区间长度判断1和0的个数
                ans += 1<<i;
        printf("%d\n", ans);
    }
    return 0;
}