C++ 查询所有子数组的 XOR 的 XOR

c++server side programmingprogramming

计算给定范围内所有子数组的 XOR 并打印。例如

输入:arr[] = { 4, 1, 2, 3, 5 }, Q = 3

查询

q1 = { 1, 2 }
q2 = { 2, 4 }
q3 = { 1, 4 }

输出:0
2
0
解释:根据给定的问题，我们需要找到给定范围内所有子数组的异或，因此对于查询 2，子数组为:
{1}, {2}, {3}, {1, 2}, {2, 3}, (1, 2, 3}
因此，您可以看到元素出现的次数为:
1 出现 3 次
2 出现 4 次
3 出现 3 次
现在我们知道异或的性质是出现偶数次的数字会被抵消，因此2 被抵消了，只剩下 3 和 1 的异或，这就是我们的答案。

我们需要观察这个问题中形成的模式，然后我们需要相应地实现它。

寻找解决方案的方法

在这个问题中，我们试图找到问题中存在的中间模式。当。当我们看到那个模式时，我们会相应地实现它并检查结果。

示例

上述方法的 C++ 代码

 
#include <bits/stdc++.h>
using namespace std;
void ansQueries(int prefeven[], int prefodd[], int l, int r){
    if ((r - l + 1) % 2 == 0) // 如果范围内存在的元素数量为偶数
        cout << &";0";
    else{
          if (l % 2 == 0) // 如果 l 为偶数
            cout << (prefeven[r] ^ prefeven[l - 1]) << &";\n";
        else // 如果 l 为奇数
            cout << (prefodd[r] ^ prefodd[l - 1]) << "\n";
    }
}
int main(){
    int arr[] = {4, 1, 2, 3, 5};
    int n = sizeof(arr) / sizeof(int); // 数组的大小
    int l[] = {1, 2, 1}; // 给定查询的左索引
    int r[] = {2, 4, 4}; // 给定查询的右索引
    int q = sizeof(l) / sizeof(int);         // 询问的查询数
    int prefodd[n] = {0}, prefeven[n] = {0}; // 偶数和奇数索引的不同前缀异或
    for (int i = 1; i <= n; i++){
          if ((i) % 2 == 0){ // 如果 i 为偶数，则我们更改 prefeven
            prefeven[i] = arr[i - 1] ^ prefeven[i - 1];
            prefodd[i] = prefodd[i - 1];
        }else{
            prefeven[i] = prefeven[i - 1];
            prefodd[i] = prefodd[i - 1] ^ arr[i - 1];
        }
    }
    for (int i = 0; i < q; i++){
        ansQueries(prefeven, prefodd, l[i], r[i]);
    }
    return 0;
}

输出

02
0

上述代码的解释

在这种方法中，我们首先观察到，如果范围的大小是偶数，那么我们的答案将为零，因为每个数字都会出现偶数次，当我们打印所有子数组时，因此通过对它们进行异或，答案将为 0，现在对于我们下一部分的范围大小为奇数，在这种情况下，出现奇数次的数字在给定范围内处于偶数位置，我们的答案将只是在给定范围内偶数位置出现的数字的异或，我们维护两个前缀数组，其中包含交替位置的异或，因为我们的 prefeven 包含所有偶数索引的异或，而 prefodd 包含所有奇数索引的异或，现在当我们解决查询时，我们只需要检查我们的 l 是偶数还是奇数并给出答案相应地。