first 题解

这道题需要处理多次区间异或查询。类似前缀和的思想，但异或运算有其特殊性：异或的逆运算是自身（即 a⊕a=0）。

解题思路：

1. 预处理前缀异或数组 prefix[i] 表示前 i 个数的异或值

2. 对于询问 [l, r]，答案为 prefix[r] ⊕ prefix[l-1]，因为区间异或 = 前缀异或的异或（自逆性质）

c++代码：

#include <iostream>
#include <vector>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    
    int n, q;
    cin >> n >> q;
    
    vector<int> prefix(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        prefix[i] = prefix[i - 1] ^ x;
    }
    
    while (q--) {
        int l, r;
        cin >> l >> r;
        cout << (prefix[r] ^ prefix[l - 1]) << '\n';
    }
    
    return 0;
}

关键点：

1. 异或运算满足：a⊕a=0，a⊕0=a，因此区间异或 = prefix[r]⊕prefix[l-1]

2. 使用 int 即可，因为 a_i≤10^9，异或结果不会超过 2^31-1

3. prefix[0]=0 便于处理 l=1 的情况

4. 时间复杂度 O(n+q)，空间复杂度 O(n)

求赞