এই সমস্যায়, আমাদের একটি N x N ম্যাট্রিক্স এবং কিছু কোয়েরি দেওয়া আছে, প্রতিটি কোয়েরি এ ম্যাট্রিক্স থেকে বने সাবম্যাট্রিক্সের টপ-লেফট এবং বটম-রাইট কর্নার ধারণ করে। আমাদের কাজ হল কোয়েরি দিয়ে ডিফাইন করা সাবম্যাট্রিক্সের সব এলিমেন্টের XOR বের করা।
একটি উদাহরণ দিয়ে সমস্যাটি বুঝতে পারি,
ইনপুট
arr[][] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}
Queries: {0,0, 1,2}, {1, 2, 2, 2}
আউটপুট
1 15
ব্যাখ্যা
query 1: 1^2^3^4^5^6 query 2: 6^9
এই সমস্যাটি সমাধান করতে, আমরা একটি প্রিফিক্স-XOR ম্যাট্রিক্স বের করব কোয়েরি সলভ করার জন্য। ম্যাট্রিক্সের (R, C) পজিশনের ভ্যালু হল টপ-লেফট কর্নার (0, 0) এবং বটম-রাইট কর্নার (R, C) পজিশনে থাকা সাব-ম্যাট্রিক্সের XOR।
আমরা প্রথমে ম্যাট্রিক্সের সব রোয়ের জন্য প্রিফিক্স-XOR বের করব একে একে। তারপর প্রতিটি কলামের জন্য প্রিফিক্স 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[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 && 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
