5207 : A08 - 2차원 구간 합 (Two Dimensional Sum)
•시간제한: 10.000 S
•메모리제한: 1024 MB
•제출: 1
•통과: 1
•만든사람: suakii
문제 설명
$H \times W$ 크기의 격자가 있습니다. 위에서 $i$ 행, 왼쪽에서 $j$ 열에 있는 칸 $ (i, j) $ 에는 정수 $X_{i,j}$ 가 적혀 있습니다.
다음 $Q$ 개의 질문에 답하는 프로그램을 작성하세요.
- $i$ 번째 질문: 왼쪽 위 $ (A_i, B_i) $ , 오른쪽 아래 $ (C_i, D_i) $ 인 직사각형 영역에 적힌 정수의 총합은?
[제약 조건]
• $1\le H,W\le 1500$
• $1\le Q\le 100000$
• $0\le X_{i,j}\le 9$
• $1\le A_i\le C_i\le H$
• $1\le B_i\le D_i\le W$
• 입력되는 모든 값은 정수입니다.
다음 $Q$ 개의 질문에 답하는 프로그램을 작성하세요.
- $i$ 번째 질문: 왼쪽 위 $ (A_i, B_i) $ , 오른쪽 아래 $ (C_i, D_i) $ 인 직사각형 영역에 적힌 정수의 총합은?
[제약 조건]
• $1\le H,W\le 1500$
• $1\le Q\le 100000$
• $0\le X_{i,j}\le 9$
• $1\le A_i\le C_i\le H$
• $1\le B_i\le D_i\le W$
• 입력되는 모든 값은 정수입니다.
입력 설명
$H$ $W$
$X_{1,1}$ $X_{1,2}$ $\dots$ $X_{1,W}$
$\dots$
$X_{H,1}$ $X_{H,2}$ $\dots$ $X_{H,W}$
$Q$
$A_1$ $B_1$ $C_1$ $D_1$
$\dots$
$A_Q$ $B_Q$ $C_Q$ $D_Q$
$X_{1,1}$ $X_{1,2}$ $\dots$ $X_{1,W}$
$\dots$
$X_{H,1}$ $X_{H,2}$ $\dots$ $X_{H,W}$
$Q$
$A_1$ $B_1$ $C_1$ $D_1$
$\dots$
$A_Q$ $B_Q$ $C_Q$ $D_Q$
출력 설명
$Q$ 줄에 걸쳐 각 질문의 답을 출력하세요.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
5 5
2 0 0 5 1
1 0 3 0 0
0 8 5 0 2
4 1 0 0 6
0 9 2 7 0
2
2 2 4 5
1 1 5 5
출력 예시
COPY
복사되었습니다!
복사되었습니다!
25
56