सी ++ में एक सबमैट्रिक्स प्रश्नों का एक्सओआर

इस समस्या में, हमें एक N x N मैट्रिक्स और कुछ प्रश्न दिए गए हैं, प्रत्येक क्वेरी में इस मैट्रिक्स से बनाए गए सबमैट्रिक्स के ऊपरी-बाएँ और निचले-दाएँ कोने होते हैं। हमारा काम क्वेरीज़ द्वारा परिभाषित सबमैट्रिक्स के सभी तत्वों के एक्सओआर को खोजना है।

समस्या को समझने के लिए एक उदाहरण लेते हैं,

इनपुट

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

इस समस्या को हल करने के लिए, हम प्रश्नों को हल करने के लिए एक उपसर्ग-एक्सओआर मैट्रिक्स पाएंगे। स्थिति (R, C) पर मैट्रिक्स का मान शीर्ष-बाएँ कोने (0, 0) से उप-मैट्रिक्स का XOR और स्थिति (R, C) पर नीचे-दाएँ कोने है।

हमें सबसे पहले उपसर्ग . मिलेगा -XOR मैट्रिक्स की सभी पंक्तियों के लिए एक-एक करके। फिर प्रत्येक कॉलम के लिए एक-एक करके उपसर्ग XOR की गणना करें।

(r1, c1) से (r2, c2) द्वारा दी गई क्वेरी के लिए उप-मैट्रिक्स के XOR को खोजने के लिए उपसर्ग का उपयोग करके गणना की जाती हैXor[r2][c2] ^ prefixXor[r1-1][c2] ^ prefixXor[r2][c1 -1] ^ उपसर्गXor[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[2]) {
   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 querries :\n";
   cout<<"Querry 1 : "<<XORSubMatrix(prefix_xor, querry1)<<endl;
   cout<<"Querry 2 : "<<XORSubMatrix(prefix_xor, querry2)<<endl;
   return 0;
}

आउटपुट

Querry 1 : 1
Querry 2 : 15