C++でのサブアレイのXOR

この問題では、配列内のLからRの範囲のarr[]といくつかのクエリが与えられます。私たちのタスクは、LからRまでのサブアレイのXORを出力することです。

問題を理解するために例を見てみましょう

入力 −配列={1、4、5、7、2、9} L =1、R =5

出力-

説明 − 4 ^ 5 ^ 7 ^ 2 ^ 9

• この問題を解決するために、次の観察に基づいて配列を作成します。

• 複数のビットをXORします。奇数の場合は、結果は1になり、そうでない場合は、結果は0になります。

次に、1のカウントを格納する2次元配列カウントを作成します。値count[i][j]は、位置i-jの1の数であり、ビットのi番目の位置にあるサブ配列arr[0..j]に存在する1の数です。サブ配列arr[L..R]のすべてのビットの1の数は、カウント配列を使用して検出されます。 arr [L ... R] =count [i] [R] --count[i][L-1]を見つける式。 1の数が奇数の場合、結果としてi番目のビットが設定されます。最終的な結果は、ビットが設定されている場合、i番目のビットに対応する2の累乗を合計することで得られます。

ソリューションの実装を示すプログラム

例

#include <bits/stdc++.h>
using namespace std;
void preProcessArray(int arr[], int n, vector<vector<int> >& cnt) {
   int i, j;
   for (i = 0; i < 32; i++) {
      cnt[i][0] = 0;
      for (j = 0; j < n; j++) {
         if (j > 0) {
            cnt[i][j] = cnt[i][j - 1];
         }
         if (arr[j] & (1 << i))
         cnt[i][j]++;
      }
   }
}
int findXORofSubArray(int L, int R, const vector<vector<int> > count) {
   int result = 0;
   int noOfOnes;
   int i, j;
   for (i = 0; i < 32; i++) {
      noOfOnes = count[i][R] - ((L > 0) ? count[i][L - 1] : 0);
      if (noOfOnes & 1) {
         result+=(1 << i);
      }
   }
   return result;
}
int main(){
   int arr[] = { 1, 4, 5, 7, 2, 9 };
   int n = sizeof(arr) / sizeof(arr[0]);
   vector<vector<int> > count(32, vector<int>(n));
   preProcessArray(arr, n, count);
   int L = 1;
   int R = 5;
   cout<<"The XOR of SubArray: "<<findXORofSubArray(L, R, count);
   return 0;
}

出力

The XOR of SubArray: 13