এই সমস্যায়, আমাদের একটি 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
এই সমস্যাটি সমাধান করার জন্য, আমরা প্রশ্নের সমাধান করার জন্য একটি উপসর্গ-XOR ম্যাট্রিক্স খুঁজে পাব। অবস্থানে ম্যাট্রিক্সের মান (R, C) উপরের-বাম কোণে (0, 0) এবং নীচের-ডান কোণে (R, C) থেকে সাব-ম্যাট্রিক্সের XOR।
আমরা প্রথমে উপসর্গ খুঁজে পাব -একের পর এক ম্যাট্রিক্সের সমস্ত সারির জন্য XOR। তারপর একে একে প্রতিটি কলামের জন্য উপসর্গ XOR গণনা করুন।
(r1, c1) থেকে (r2, c2) প্রদত্ত একটি প্রশ্নের সাব-ম্যাট্রিক্সের XOR খুঁজে বের করার জন্য প্রিফিক্সএক্সর [r2][c2] ^ উপসর্গ ব্যবহার করে গণনা করা হয় [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[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