在C ++中给定范围内出现偶数次的数字的XOR
在这个问题中，我们给了一个由n个元素组成的数组，并且存在一些查询，这些查询的范围从数组的起点到终点。我们的任务是两个发现在该范围内甚至出现多次的元素的XOR。
让我们举个例子来了解这个问题，
输入-
array = {1, 2, 3, 1, 1, 2, 2, 3}
querries = 2
R = 4
L = 2, R = 5
L = 2, R = 7输出-
0 1 0
这个问题的解决方案很容易，我们将通过每个查询找到给定范围内的所有数组元素的XOR之和。为此，我们将使用前缀和xor。
示例
显示我们解决方案实施情况的程序，
#include <bits/stdc++.h>
using namespace std;
struct que {
int L, R, idx;
};
bool cmp(que a, que b){
if (a.R != b.R)
return a.R < b.R;
else
return a.L < b.L;
}
int findXORSum(int BIT[], int index){
int xorSum = 0;
index = index + 1;
while (index > 0){
xorSum ^= BIT[index];
index -= index & (-index);
}
return xorSum;
}
void updateBIT(int BIT[], int N, int index, int val){
index = index + 1;
while (index <= N){
BIT[index] ^= val;
index += index & (-index);
}
}
int* createBitTree(int arr[], int N){
int* BIT = new int[N + 1];
for (int i = 1; i <= N; i++)
BIT[i] = 0;
return BIT;
}
void findXORSolution(int arr[], int N, que queries[], int Q, int BIT[]){
int* prefixXOR = new int[N + 1];
map<int, int> XORval;
for (int i = 0; i < N; i++) {
if (!XORval[arr[i]])
XORval[arr[i]] = i;
if (i == 0)
prefixXOR[i] = arr[i];
else
prefixXOR[i] = prefixXOR[i - 1] ^ arr[i];
}
int lastOcc[1000001];
memset(lastOcc, -1, sizeof(lastOcc));
sort(queries, queries + Q, cmp);
int res[Q];
int j = 0;
for (int i = 0; i < Q; i++){
while (j <= queries[i].R){
if (lastOcc[XORval[arr[j]]] != -1)
updateBIT(BIT, N, lastOcc[XORval[arr[j]]], arr[j]);
updateBIT(BIT, N, j, arr[j]);
lastOcc[XORval[arr[j]]] = j;
j++;
}
int allXOR = prefixXOR[queries[i].R] ^ prefixXOR[queries[i].L - 1];
int distinctXOR = findXORSum(BIT, queries[i].R) ^ findXORSum(BIT, queries[i].L - 1);
res[queries[i].idx] = allXOR ^ distinctXOR;
}
for (int i = 0; i < Q; i++)
cout << res[i] << endl;
}
int main() {
int arr[] = {1, 2, 1, 1, 2, 2, 3, 1, 3};
int N = sizeof(arr) / sizeof(arr[0]);
int* BIT = createBitTree(arr, N);
que queries[4];
queries[0].L = 1;
queries[0].R = 4; queries[0].idx = 0;
queries[1].L = 2;
queries[1].R = 7, queries[1].idx = 1;
queries[2].L = 0;
queries[2].R = 3, queries[2].idx = 2;
queries[3].L = 3;
queries[3].R = 6, queries[3].idx = 3;
int Q = sizeof(queries) / sizeof(queries[0]);
cout<<"Xor sum for all queries is \n";
findXORSolution(arr, N, queries, Q, BIT);
return 0;
}输出结果
Xor sum for all queries is 3 2 0 2