주어진 범위에 있는 모든 하위 배열의 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
위 코드 설명
이 접근 방식에서 우리는 먼저 범위의 크기가 짝수이면 모든 하위 배열을 인쇄할 때 모든 숫자가 짝수 번 나타나기 때문에 답이 0이 될 것이라는 점을 먼저 관찰합니다. 여기서 범위의 크기는 홀수입니다. 이 경우 홀수로 나타나는 숫자는 주어진 범위의 짝수 위치에 있고 우리의 대답은 단순히 주어진 범위의 짝수 위치에 나타나는 숫자의 XOR이 될 것입니다. 2 우리는 두 개의 접두사를 유지합니다 우리의 prefeven은 모든 짝수 인덱스의 XOR을 포함하고 prefodd는 모든 홀수 인덱스의 XOR을 포함하므로 대체 위치의 XOR을 포함하는 배열은 이제 쿼리를 해결할 때 l이 짝수인지 홀수인지 확인하고 그에 따라 답을 주기만 하면 됩니다. .
결론
이 자습서에서는 모든 하위 배열의 XOR에 대한 쿼리를 해결하는 문제를 해결합니다. 우리는 또한 이 문제에 대한 C++ 프로그램과 이 문제를 해결한 완전한 접근 방식( Normal)을 배웠습니다. C, Java, python 및 기타 언어와 같은 다른 언어로 동일한 프로그램을 작성할 수 있습니다. 이 튜토리얼이 도움이 되기를 바랍니다.