3206 : 2차원 누적 합2
•시간제한: 1.000 S
•메모리제한: 256 MB
•제출: 5
•통과: 2
•만든사람: suakii
문제 설명
[3173번 2차원 누적 합의 심화 문제입니다.]
$N \times M$ 크기의 2차원 배열이 주어지고, $Q$개의 쿼리가 주어집니다.
각 쿼리는 $(r_1, c_1, r_2, c_2)$이며, 좌상단 $(r_1, c_1)$에서 우하단 $(r_2, c_2)$까지의 직사각형 영역의 합을 구하세요. (1-indexed)
배열의 크기와 쿼리의 개수 $Q$가 크기 때문에, 각 쿼리마다 반복문을 수행하는 완전 탐색($O(Q \times N \times M)$) 방식은 시간 초과(TLE)를 받게 됩니다.
전처리 단계에서 2차원 누적 합(Prefix Sum) 배열을 구성하여 각 쿼리를 $O(1)$에 해결하세요.
[제약 조건]
• $1 \le N, M \le 300$
• $1 \le Q \le 50000$
• $0 \le (\text{각 격자 원소}) \le 100$
• $1 \le r_1 \le r_2 \le N$, $1 \le c_1 \le c_2 \le M$
• 입력되는 모든 값은 정수
입력 설명
첫째 줄에 , M, Q 공백으로 구분되어 주어집니다.
둘째 줄부터 줄에 걸쳐 정수가 공백으로 구분되어 주어집니다.
그 다음 줄에 걸쳐 , c_1, r_2, c_2 공백으로 구분되어 주어집니다.
둘째 줄부터 줄에 걸쳐 정수가 공백으로 구분되어 주어집니다.
그 다음 줄에 걸쳐 , c_1, r_2, c_2 공백으로 구분되어 주어집니다.
출력 설명
각 쿼리의 결과를 한 줄씩 출력하세요.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
3 3 2
1 2 3
4 5 6
7 8 9
1 1 2 2
2 2 3 3
출력 예시
COPY
복사되었습니다!
복사되었습니다!
12
28