XOR truy vấn ma trận con (submatrix) C++

Trong bài toán này, cho ma trận N x N và các truy vấn, mỗi truy vấn chứa góc trên-trái và góc dưới-phải của ma trận con. Nhiệm vụ tìm XOR tất cả phần tử của ma trận con theo truy vấn.

Ví dụ:

Input

arr[][] = {{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}
Truy vấn: {0,0, 1,2}, {1, 2, 2, 2}

Output

1 15

Giải thích

Truy vấn 1: 1^2^3^4^5^6
Truy vấn 2: 6^9

Giải pháp: xây dựng ma trận prefix-XOR. Giá trị tại (R,C) = XOR ma trận con từ (0,0) đến (R,C). Tính prefix-XOR hàng rồi cột. XOR ma trận con (r1,c1) đến (r2,c2) = prefix[r2][c2] ^ prefix[r1-1][c2] ^ prefix[r2][c1-1] ^ prefix[r1-1][c1-1].

Ví dụ minh họa

#include <iostream>
using namespace std;

#define n 3

void preXOR(int arr[][n], int prefix_xor[][n]) {
    // Prefix XOR theo hàng
    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]);
        }
    
    // Prefix XOR theo cột
    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 query[4]) {
    int xor_1 = 0, xor_2 = 0, xor_3 = 0;
    
    if (query[0] != 0)
        xor_1 = prefix_xor[query[0] - 1][query[3]];
    if (query[1] != 0)
        xor_2 = prefix_xor[query[2]][query[1] - 1];
    if (query[0] != 0 && query[1] != 0)
        xor_3 = prefix_xor[query[0] - 1][query[1] - 1];
    
    return ((prefix_xor[query[2]][query[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 query1[] = {0, 0, 2, 2};
    int query2[] = {1, 2, 2, 2};
    
    cout << "XOR ma trận con theo truy vấn:\n";
    cout << "Truy vấn 1: " << XORSubMatrix(prefix_xor, query1) << endl;
    cout << "Truy vấn 2: " << XORSubMatrix(prefix_xor, query2) << endl;
    
    return 0;
}

Kết quả

Truy vấn 1: 1
Truy vấn 2: 15