8074 : 2D 구간 합 쿼리
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
$N \times M$ 크기의 정수 격자가 주어집니다.
이후 $Q$개의 쿼리가 주어지며, 각 쿼리는 부분 직사각형 영역의 원소 합을 구하는 것입니다.
2차원 누적 합(Prefix Sum)을 이용하여 각 쿼리를 $O(1)$에 처리하는 프로그램을 작성하십시오.
[제약 조건]
• $1 \le N, M \le 500$
• $1 \le Q \le 30{,}000$
• $-100 \le A_{ij} \le 100$
• $1 \le r_1 \le r_2 \le N$, $1 \le c_1 \le c_2 \le M$
이후 $Q$개의 쿼리가 주어지며, 각 쿼리는 부분 직사각형 영역의 원소 합을 구하는 것입니다.
2차원 누적 합(Prefix Sum)을 이용하여 각 쿼리를 $O(1)$에 처리하는 프로그램을 작성하십시오.
[제약 조건]
• $1 \le N, M \le 500$
• $1 \le Q \le 30{,}000$
• $-100 \le A_{ij} \le 100$
• $1 \le r_1 \le r_2 \le N$, $1 \le c_1 \le c_2 \le M$
입력 설명
첫째 줄에 행의 수 $N$, 열의 수 $M$, 쿼리의 수 $Q$가 공백으로 구분되어 주어집니다. ($1 \le N, M \le 500$, $1 \le Q \le 30{,}000$)
다음 $N$개의 줄에 걸쳐 격자의 각 행이 주어집니다. 각 행은 $M$개의 정수로 구성됩니다. ($-100 \le A_{ij} \le 100$)
다음 $Q$개의 줄에 걸쳐 각 쿼리 $(r_1, c_1, r_2, c_2)$가 주어집니다. 이는 행 $r_1$, 열 $c_1$부터 행 $r_2$, 열 $c_2$까지의 부분 직사각형을 의미합니다. ($1 \le r_1 \le r_2 \le N$, $1 \le c_1 \le c_2 \le M$)
다음 $N$개의 줄에 걸쳐 격자의 각 행이 주어집니다. 각 행은 $M$개의 정수로 구성됩니다. ($-100 \le A_{ij} \le 100$)
다음 $Q$개의 줄에 걸쳐 각 쿼리 $(r_1, c_1, r_2, c_2)$가 주어집니다. 이는 행 $r_1$, 열 $c_1$부터 행 $r_2$, 열 $c_2$까지의 부분 직사각형을 의미합니다. ($1 \le r_1 \le r_2 \le N$, $1 \le c_1 \le c_2 \le M$)
출력 설명
각 쿼리에 대해 부분 직사각형 내 원소들의 합을 한 줄에 하나씩 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
3 3 2
1 2 3
4 5 6
7 8 9
1 1 2 2
2 2 3 3
출력 예시
COPY
복사되었습니다!
복사되었습니다!
12
28도움
2차원 누적 합 배열 $P[i][j] = \sum_{r=1}^{i} \sum_{c=1}^{j} A[r][c]$를 $O(NM)$에 구축합니다.
이후 임의의 부분 직사각형 $(r_1, c_1, r_2, c_2)$의 합은 $P[r_2][c_2] - P[r_1-1][c_2] - P[r_2][c_1-1] + P[r_1-1][c_1-1]$로 $O(1)$에 계산됩니다.
이후 임의의 부분 직사각형 $(r_1, c_1, r_2, c_2)$의 합은 $P[r_2][c_2] - P[r_1-1][c_2] - P[r_2][c_1-1] + P[r_1-1][c_1-1]$로 $O(1)$에 계산됩니다.