すべてのサブアレイのXORのXORに関するC++クエリ

指定された範囲に存在するすべてのサブアレイのXORを計算し、それを出力します。例

Input : arr[] = { 4, 1, 2, 3, 5 }, Q = 3

Queries

q1 = { 1, 2 }
q2 = { 2, 4 }
q3 = { 1, 4 }

Output : 0
2
0
Explanation : As the given problem states that we need to find XOR of all the subarrays present in the given range so as for query 2 the subarrays are :
{1}, {2}, {3}, {1, 2}, {2, 3}, (1, 2, 3}
So as you can see the number of occurrences of elements are :
1 is present 3 times
2 is present 4 times
3 is present 3 times
Now as we know the property of XOR is that the numbers that are present an even number of times get canceled out so out 2 got canceled out and just the XOR of 3 and 1 remained and that was our answer.

この問題で形成されるパターンを観察し、それに応じて実装する必要があります。

解決策を見つけるためのアプローチ

この問題では、問題に存在する中間パターンを見つけようとしています。いつ。そのパターンを確認したら、それに応じて実装し、結果を確認します。

例

上記のアプローチのC++コード

 
#include <bits/stdc++.h>
using namespace std;
void ansQueries(int prefeven[], int prefodd[], int l, int r){
    if ((r - l + 1) % 2 == 0) // if number of element present in the range is even
        cout << "0";
    else{
        if (l % 2 == 0) // if l is even
            cout << (prefeven[r] ^ prefeven[l - 1]) << "\n";
        else // if l is odd
            cout << (prefodd[r] ^ prefodd[l - 1]) << "\n";
    }
}
int main(){
    int arr[] = {4, 1, 2, 3, 5};
    int n = sizeof(arr) / sizeof(int); // size of our array
    int l[] = {1, 2, 1}; // given queries' left index
    int r[] = {2, 4, 4}; // given queries' right index
    int q = sizeof(l) / sizeof(int);         // number of queries asked
    int prefodd[n] = {0}, prefeven[n] = {0}; // different prefix xor for even and odd indices
    for (int i = 1; i <= n; i++){
        if ((i) % 2 == 0){ // if i is even then we change prefeven
            prefeven[i] = arr[i - 1] ^ prefeven[i - 1];
            prefodd[i] = prefodd[i - 1];
        }else{
            prefeven[i] = prefeven[i - 1];
            prefodd[i] = prefodd[i - 1] ^ arr[i - 1];
        }
    }
    for (int i = 0; i < q; i++){
        ansQueries(prefeven, prefodd, l[i], r[i]);
    }
    return 0;
}

出力

02
0

上記のコードの説明

このアプローチでは、最初に、範囲のサイズが偶数の場合、すべてのサブ配列を印刷するときにすべての数値が偶数回表示されるため、回答がゼロになることを確認します。したがって、XORを取得することで、次の部分の回答は0になります。範囲のサイズが奇数の場合、この場合、奇数回表示される数値は指定された範囲の偶数の位置にあり、答えは単純に、指定された範囲2の偶数の位置に表示される数値のXORです。2つのプレフィックスを維持します。 prefevenにはすべての偶数インデックスのXORが含まれ、prefoddにはすべての奇数インデックスのXORが含まれるため、代替位置のXORを含む配列クエリを解決するときは、lが偶数か奇数かを確認し、それに応じて答えを出す必要があります。 。

結論

このチュートリアルでは、すべてのサブアレイのXORのXORに関するクエリを解決するための問題を解決します。また、この問題のC ++プログラムと、この問題を解決するための完全なアプローチ（Normal）についても学びました。同じプログラムを、C、java、python、その他の言語などの他の言語で作成できます。このチュートリアルがお役に立てば幸いです。