C++の特定の範囲に偶数回出現した数値の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