এই সমস্যায়, আমাদেরকে 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
