ในปัญหานี้ เราได้รับอาร์เรย์ขององค์ประกอบ 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 ขององค์ประกอบทั้งหมดของอาร์เรย์ภายในช่วงที่กำหนดโดยการค้นหาแต่ละครั้ง สำหรับสิ่งนี้ เราจะใช้คำนำหน้า sum 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
