10-2: 직사각형의 합

직사각형의 합

 

문제

---

N(Row) x M(Col) 의 직사각형이 주어지며, 각 칸에는 정수가 들어있다. 이제 Q개의 질문에 대하여 답을 해야 하며, 각각의 질문은 (a, b)부터 (c, d)까지의 직사각형에 들어있는 정수의 합을 묻는다. 예를 들어, 다음과 같이 5 x 5 의 직사각형이 주어질 때, (1, 2) 부터 (3, 3) 까지의 직사각형에 들어있는 정수의 합은 26 이다.

 

입력

---

첫 번째 줄에 N, M, Q가 주어진다. ( 1 ≤ N, M ≤ 1,000, 1 ≤ Q ≤ 1,000,000 ) 두 번째 줄부터 N x M 직사각형에 주어진다. 그 후 Q개의 질문이 주어진다. 각각의 질문은 “a b c d” 로 이루어 져 있으며, 이는 (a, b) 부터 (c, d) 까지의 직사각형에 들어있는 정수의 합을 묻는다.  

출력

---

각 질문에 대한 답을 출력한다.

 

예제 입력

5 5 3
 1 -2 3 2 8
-8 -9 3 4 5
 2 4 7 8 2
 1 4 3 1 4
-1 2 5 -6 3
1 2 3 4
0 0 1 1
2 0 2 1

예제 출력

37
-18
6

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class dp_rectsum {

    /**
     * 직사각형의 합
     *
     *
     * 문제
     * N(Row) x M(Col) 의 직사각형이 주어지며, 각 칸에는 정수가 들어있다.
     * 이제 Q개의 질문에 대하여 답을 해야 하며, 각각의 질문은 (a, b)부터 (c, d)까지의 직사각형에 들어있는 정수의 합을 묻는다.
     *
     * 예를 들어, 다음과 같이 5 x 5 의 직사각형이 주어질 때, (1, 2) 부터 (3, 3) 까지의 직사각형에 들어있는 정수의 합은 26 이다.
     * 문제:
     *
     *
     * 입력:
     * 첫 번째 줄에 N, M, Q가 주어진다. ( 1 ≤ N, M ≤ 1,000, 1 ≤ Q ≤ 1,000,000 )
     * 두 번째 줄부터 N x M 직사각형에 주어진다. 그 후 Q개의 질문이 주어진다. 각각의 질문은 “a b c d” 로 이루어 져 있으며, 이는 (a, b) 부터 (c, d) 까지의 직사각형에 들어있는 정수의 합을 묻는다.
     *
     * 출력:
     *
     *
     * 예제 입력:
     *
     * 5 5 3
     *  1 -2 3 2 8
     * -8 -9 3 4 5
     *  2 4 7 8 2
     *  1 4 3 1 4
     * -1 2 5 -6 3
     * 1 2 3 4
     * 0 0 1 1
     * 2 0 2 1
     *
     *
     * 예제 출력:
     * 37
     * -18
     * 6
     *
     * @param args
     */

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(st.nextToken());
        int Q = Integer.parseInt(st.nextToken());
        int[][] sum = new int[N][M];

        for (int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            for (int j=0;j<M; j++) {
                int rectElement = Integer.parseInt(st.nextToken());
                if (i==0 && j==0){
                    sum[0][0] = rectElement;
                }else if (i==0){
                    sum[0][j] = rectElement + sum[0][j-1];
                } else if (j==0){
                    sum[i][0] = rectElement + sum[i-1][0];
                } else{
                    sum[i][j] = sum[i][j-1] + sum[i-1][j] + rectElement - sum[i-1][j-1];
                }
            }
        }

        for (int i=0; i<Q; i++){
            st = new StringTokenizer(br.readLine());
            int a = Integer.parseInt(st.nextToken());
            int b = Integer.parseInt(st.nextToken());
            int c = Integer.parseInt(st.nextToken());
            int d = Integer.parseInt(st.nextToken());

            int sumInRange;
            if (a>=1 && b>=1){

                sumInRange = sum[c][d] - sum[a-1][d] - sum[c][b-1] + sum[a-1][b-1];
            } else if (a>=1){
                sumInRange = sum[c][d] - sum[a-1][d];
            } else if (b>=1){
                sumInRange = sum[c][d] - sum[c][b-1];
            } else {
                sumInRange = sum[c][d];
            }


            System.out.println(sumInRange);
        }

    }
}