XOR của các số xuất hiện với số lần chẵn trong Dải ô đã cho trong C ++

Trong bài toán này, chúng ta được cung cấp một mảng gồm n phần tử và có một số truy vấn nằm trong phạm vi từ điểm đầu đến điểm cuối trong mảng. Nhiệm vụ của chúng tôi là hai tìm XOR của các phần tử xuất hiện chẵn một số lần trong phạm vi.

Hãy lấy một ví dụ để hiểu vấn đề,

Đầu vào -

array = {1, 2, 3, 1, 1, 2, 2, 3}
querries = 2
R = 4
L = 2, R = 5
L = 2, R = 7

Đầu ra -

0
1
0

Giải pháp cho vấn đề này khá dễ dàng, chúng ta sẽ tìm tổng XOR của tất cả các phần tử của mảng trong phạm vi đã cho bằng mỗi truy vấn. Đối với điều này, chúng tôi sẽ sử dụng tiền tố sum xor.

Ví dụ

Chương trình cho thấy việc triển khai giải pháp của chúng tôi,

#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;
}

Đầu ra

Xor sum for all queries is
3
2
0
2