题目链接：牛客 18979

给定一个长度为 n 的整数数组，每次询问一个区间 [l, r]，要求找到一个满足 0 ≤ x < 2^31 的整数 x，使区间内所有 x XOR a[i] 的和最大。如果有多个 x 能取得最大值，输出其中最小的一个。

数组长度和询问次数都不超过 10^5，数组元素满足 1 ≤ a[i] ≤ 10^9。

这道题的关键是：异或可以逐位分析，而区间内每一位的 1 的数量可以用前缀和快速统计。

一、把异或和拆成每一位的贡献

异或的规则是：相同为 0，不同为 1。

0 XOR 0 = 0
0 XOR 1 = 1
1 XOR 0 = 1
1 XOR 1 = 0

对于二进制第 b 位（最低位编号为 0），设区间内这一位为 1 的元素有 ones 个，为 0 的元素有 zeros 个：

len = r - l + 1
zeros = len - ones

如果 x 的第 b 位取 0，那么原来这一位为 1 的元素异或后仍为 1，这一位对总和的贡献为：

ones × 2^b

如果 x 的第 b 位取 1，那么原来这一位为 0 的元素异或后变成 1，这一位对总和的贡献为：

zeros × 2^b

因此，选择规则是：

• zeros > ones：x 的这一位取 1。
• zeros < ones：x 的这一位取 0。
• zeros == ones：两种选择贡献相同，为了让 x 最小，取 0。

合并起来就是：只有 zeros > ones 时，才把 x 的这一位置为 1。

代码可以写成：

if (ones * 2 < len) {
    // x 的第 b 位取 1
}

二、为什么每一位可以独立决定？

一个非负整数的值，等于它每一位的二进制数字乘以对应权值，再将这些贡献相加。因此，题目中的总和可以重新整理为：

总和 = 第 0 位的总贡献 + 第 1 位的总贡献 + … + 第 30 位的总贡献

选择 x 的第 b 位，只影响异或结果的第 b 位，不会改变其他位的异或结果。虽然最后做加法时可能产生进位，但进位只是数值的表示过程，不会改变上述贡献之和。

同时，0 ≤ x < 2^31 允许低 31 位任意组合，各位之间没有额外约束。所以，让每一位的贡献分别最大，就能让总和最大。

在贡献相同的位上取 0，不影响最大总和，还能使 x 最小。

三、用前缀和统计区间内的 1

如果每次询问都遍历整个区间，最坏需要处理约 n × q 个元素，无法满足数据规模。

我们为每一个二进制位建立前缀和：

pre[i][b]：数组前 i 个元素中，第 b 位为 1 的元素个数

初始状态为：

pre[0][b] = 0;

递推公式为：

pre[i][b] = pre[i - 1][b] + ((a[i] >> b) & 1);

其中，(a[i] >> b) & 1 用来取出 a[i] 的第 b 位，结果为 0 或 1。

这样，区间 [l, r] 内第 b 位为 1 的元素个数就能直接计算：

int ones = pre[r][b] - pre[l - 1][b];

数组下标从 1 开始，当 l 为 1 时使用 pre[0][b]，也不会出现负下标。

四、如何构造答案？

这里采用从高位到低位的写法。每确定一位，就先把已有答案左移一位，再把当前位追加到最低位：

ans <<= 1;
if (ones * 2 < len) {
    ans += 1;
}

例如，要依次构造二进制数字 1、0、1：

初始：0
加入 1：1
加入 0：10
加入 1：101

这种构造方式要求按第 30 位到第 0 位的顺序处理，因为先加入的数字会随着后续左移移向高位。

也可以直接设置对应位：

if (ones * 2 < len) {
    ans |= (1 << b);
}

这种写法不会移动已经确定的位，所以遍历顺序可以从低位到高位，也可以从高位到低位。

五、完整代码

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

const int MAXN = 100000 + 5;
const int BITS = 31;

// 全局数组默认初始化为 0。
int pre[MAXN][BITS];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    cin >> n;

    for (int i = 1; i <= n; i++) {
        int value;
        cin >> value;

        for (int b = 0; b < BITS; b++) {
            pre[i][b] = pre[i - 1][b] + ((value >> b) & 1);
        }
    }

    int q;
    cin >> q;

    while (q--) {
        int l, r;
        cin >> l >> r;

        int len = r - l + 1;
        int ans = 0;

        for (int b = BITS - 1; b >= 0; b--) {
            int ones = pre[r][b] - pre[l - 1][b];

            // 从高位到低位追加当前位。
            ans <<= 1;

            // 0 的数量严格多于 1 时，当前位取 1。
            if (ones * 2 < len) {
                ans += 1;
            }
        }

        cout << ans << '\n';
    }

    return 0;
}

六、复杂度分析

• 预处理：每个元素处理 31 个二进制位，时间复杂度为 O(31n)。
• 单次询问：枚举 31 个二进制位，时间复杂度为 O(31)。
• 总时间复杂度：O(31(n + q))。
• 空间复杂度：O(31n)。

七、几个容易写错的地方

1. 不能直接判断 ones < len / 2

C++ 中，两个整数相除会舍去小数部分。

例如区间长度为 3，某一位有 1 个 1、2 个 0，此时应当将 x 的这一位置为 1。但：

1 < 3 / 2   // 等价于 1 < 1，结果为 false

当区间只有一个元素时，这个错误也会出现：若该位的 ones 为 0，判断会变成 0 < 0。

正确写法是：

ones * 2 < len

或者直接比较两种数字的数量：

ones < len - ones

也不能简单改成 ones <= len / 2，因为区间长度为偶数且 0、1 数量相等时，应当取 0。

2. 数量相等时，取 1 不会让总和更大

只看某一位，假设两个元素在这一位上分别为 0 和 1：

x 的这一位取 0：异或后的两位为 0、1
x 的这一位取 1：异或后的两位为 1、0

一个元素的贡献增加了，另一个元素的贡献恰好减少相同的量，所以总贡献不变。此时取 0，是为了满足“最大总和对应的最小 x”。

3. ans << 1 不会修改 ans

ans << 1;   // 计算左移结果，但没有保存
ans <<= 1;  // 将左移结果赋回 ans

用左移追加位时，无论当前位取 0 还是取 1，都必须进行这次左移。

4. 只处理第 0～30 位，但不能漏掉第 30 位

题目要求 x < 2^31，因此 x 使用的是第 0～30 位，共 31 位。

虽然数组元素不超过 10^9，第 30 位始终为 0，但 x 的这一位仍然可以取 1，而且取 1 会增加区间内每一个异或结果。因此，第 30 位必须处理。

对于 pre[][32]，访问下标 31 本身没有越过数组边界，但这一位不属于允许的 x 的范围，也不应参与答案构造。

5. 输出 x，不需要计算最大异或和

x 最大为 2^31 - 1，在常见竞赛环境的 32 位有符号 int 范围内。代码从高位到低位构造 31 位答案，中间结果也不会超过这个范围。

如果另外计算整个区间的异或和，总和可能超过 int 范围，就需要使用 long long。本题只要求输出 x，因此没有必要实际计算这个总和。