इस समस्या में, हमें एक N x N मैट्रिक्स और कुछ क्वेरीज दी गई हैं, प्रत्येक क्वेरी में इस मैट्रिक्स से बने सबमैट्रिक्स का टॉप-लेफ्ट और बॉटम-राइट कॉर्नर होता है। हमारा कार्य क्वेरीज द्वारा परिभाषित सबमैट्रिक्स के सभी तत्वों का XOR खोजना है।
आइए एक उदाहरण से समस्या को समझते हैं,
इनपुट
arr[][] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}
Querries: {0,0, 1,2}, {1, 2, 2, 2}
आउटपुट
1 15
व्याख्या
querry 1: 1^2^3^4^5^6 querry 2: 6^9
इस समस्या को हल करने के लिए, हम क्वेरीज को हल करने के लिए एक prefix-XOR मैट्रिक्स ढूंढेंगे। मैट्रिक्स में स्थिति (R, C) पर मान टॉप-लेफ्ट कॉर्नर (0, 0) और बॉटम-राइट कॉर्नर स्थिति (R, C) से सब-मैट्रिक्स का XOR है।
हम पहले मैट्रिक्स की सभी पंक्तियों के लिए एक-एक करके prefix-XOR ढूंढेंगे। फिर प्रत्येक कॉलम के लिए एक-एक करके prefix XOR की गणना करेंगे।
क्वेरी (r1, c1) से (r2, c2) द्वारा दिए गए सब-मैट्रिक्स का XOR prefixXor[r2][c2] ^ prefixXor[r1-1][c2] ^ prefixXor[r2][c1-1] ^ prefixXor[r1-1][c1-1] का उपयोग करके गणना की जाती है।
हमारे समाधान के कार्यान्वयन को दिखाने वाला प्रोग्राम,
उदाहरण
#include <iostream>
using namespace std;
#define n 3
void preXOR(int arr[][n], int prefix_xor[][n]) {
for (int i = 0; i < n; i++)
for (int j = 0; j < n; j++) {
if (j == 0)
prefix_xor[i][j] = arr[i][j];
else
prefix_xor[i][j] = (prefix_xor[i][j - 1] ^ arr[i][j]);
}
for (int i = 0; i < n; i++)
for (int j = 1; j < n; j++)
prefix_xor[j][i] = (prefix_xor[j - 1][i] ^ prefix_xor[j][i]);
}
int XORSubMatrix(int prefix_xor[][n], int querry[4]) {
int xor_1 = 0, xor_2 = 0, xor_3 = 0;
if (querry[0] != 0)
xor_1 = prefix_xor[querry[0] - 1][querry[3]];
if (querry[1] != 0)
xor_2 = prefix_xor[querry[2]][querry[1] - 1];
if (querry[2] != 0 and querry[1] != 0)
xor_3 = prefix_xor[querry[0] - 1][querry[1] - 1];
return ((prefix_xor[querry[2]][querry[3]] ^ xor_1) ^ (xor_2 ^ xor_3));
}
int main() {
int arr[][n] = {{1, 2, 3},
{4, 5, 6},
{7, 8, 9}};
int prefix_xor[n][n];
preXOR(arr, prefix_xor);
int querry1[] = {0, 0, 2, 2};
int querry2[] = {1, 2, 2, 2};
cout << "The XOR of submatrix created by queries:\n";
cout << "Query 1: " << XORSubMatrix(prefix_xor, querry1) << endl;
cout << "Query 2: " << XORSubMatrix(prefix_xor, querry2) << endl;
return 0;
}
आउटपुट
Query 1: 1 Query 2: 15
