문제 소개
이 문제에서는 N×N 크기의 행렬과 여러 개의 쿼리가 주어집니다. 각 쿼리는 행렬에서 잘라낸 부분 행렬의 왼쪽 위 좌표와 오른쪽 아래 좌표를 담고 있으며, 우리의 과제는 해당 부분 행렬에 포함된 모든 원소의 XOR 값을 구하는 것입니다.
예시를 통해 문제를 자세히 살펴보겠습니다.
입력
arr[][] = {{1, 2, 3}
{4, 5, 6}
{7, 8, 9}}
쿼리: {0, 0, 1, 2}, {1, 2, 2, 2}
출력
7 15
설명
쿼리 1 : 1^2^3^4^5^6 = 7 쿼리 2 : 6^9 = 15
접근 방법: 접두사 XOR(Prefix-XOR) 행렬 활용
이 문제는 접두사 XOR(prefix-XOR) 행렬을 미리 계산해 두면 각 쿼리를 상수 시간(O(1))에 처리할 수 있습니다. 접두사 XOR 행렬에서 위치 (R, C)의 값은 왼쪽 위 모서리 (0, 0)부터 오른쪽 아래 모서리 (R, C)까지의 부분 행렬 전체 원소들의 XOR 값입니다.
계산은 다음 두 단계로 진행합니다.
행 방향 계산: 행렬의 각 행에 대해 왼쪽에서 오른쪽으로 접두사 XOR을 차례대로 구합니다.
열 방향 계산: 그다음 각 열에 대해 위에서 아래로 접두사 XOR을 다시 누적합니다.
이렇게 하면 prefix_xor[R][C]에는 (0, 0)부터 (R, C)까지 영역의 전체 XOR이 저장됩니다.
쿼리 처리 공식
(r1, c1)부터 (r2, c2)까지의 부분 행렬 XOR은 포함-배제 원리를 이용해 다음과 같이 구할 수 있습니다.
결과 = prefixXor[r2][c2] ^ prefixXor[r1-1][c2] ^ prefixXor[r2][c1-1] ^ prefixXor[r1-1][c1-1]
여기서 r1 또는 c1이 0이라 대응하는 항의 인덱스가 음수가 되는 경우에는 해당 항을 제외하고 계산합니다.
구현 예제
#include <iostream>
using namespace std;
#define n 3
// 접두사 XOR 행렬을 생성하는 함수
void preXOR(int arr[][n], int prefix_xor[][n]) {
// 1단계: 각 행에 대해 왼쪽에서 오른쪽으로 접두사 XOR 계산
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]);
}
// 2단계: 각 열에 대해 위에서 아래로 접두사 XOR 누적
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]);
}
// 쿼리 범위 (r1, c1) ~ (r2, c2)의 부분 행렬 XOR을 반환하는 함수
int XORSubMatrix(int prefix_xor[][n], int query[4]) {
int total = prefix_xor[query[2]][query[3]];
int top = 0, left = 0, corner = 0;
if (query[0] != 0)
top = prefix_xor[query[0] - 1][query[3]];
if (query[1] != 0)
left = prefix_xor[query[2]][query[1] - 1];
if (query[0] != 0 && query[1] != 0)
corner = prefix_xor[query[0] - 1][query[1] - 1];
return ((total ^ top) ^ (left ^ corner));
}
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, 1, 2};
int query2[] = {1, 2, 2, 2};
cout<<"부분 행렬 쿼리의 XOR 결과 :\n";
cout<<"쿼리 1 : "<<XORSubMatrix(prefix_xor, query1)<<endl;
cout<<"쿼리 2 : "<<XORSubMatrix(prefix_xor, query2)<<endl;
return 0;
}
출력
쿼리 1 : 7 쿼리 2 : 15
복잡도 분석
시간 복잡도: 접두사 XOR 행렬을 생성하는 데 O(N²)이 소요되며, 이후 각 쿼리는 O(1)에 처리됩니다. 따라서 Q개의 쿼리를 처리하는 전체 시간 복잡도는 O(N² + Q)입니다.
공간 복잡도: 접두사 XOR 행렬을 저장하기 위해 O(N²)의 추가 공간이 필요합니다.