직사각형의 합

직사각형의 합

 

문제

---

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.util.*;

public class Main {

    public static ArrayList<Integer> box = new ArrayList<>();
    public static long finalResult = 0;

    //    public static long max = Integer.MIN_VALUE;
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //총 몇개의 숫자를 입력 받을 것인지
        int a;
        int b;
        int c;
        long d[][];
        long e[][];
        int count = 0;
        long max = Integer.MIN_VALUE;
        a = sc.nextInt();
        b = sc.nextInt();

        c = sc.nextInt();

        e = new long[a][b];

        for (int i = 0; i < a; i++) {
            for (int j = 0; j < b; j++) {
                int thisN = sc.nextInt();

                long left;
                if (j > 0) left = e[i][j - 1];
                else left = 0;

                long up;
                if (i > 0) up = e[i - 1][j];
                else up = 0;

                long sideUP;
                if (i > 0 && j > 0) sideUP = e[i - 1][j - 1];
                else sideUP = 0;

                e[i][j] = left + up + thisN - sideUP;
            }
        }

        for (int i = 0; i < c; i++) {
            int x1 = sc.nextInt();
            int y1 = sc.nextInt();
            int x2 = sc.nextInt();
            int y2 = sc.nextInt();

            long bigBox = e[x2][y2];

            long rightBox;
            if (y1 > 0) rightBox = e[x2][y1 - 1];
            else rightBox = 0;

            long upBox;
            if (x1 > 0) upBox = e[x1 - 1][y2];
            else upBox = 0;

            long sideUPBox;
            if (x1 > 0 && y1 > 0) sideUPBox = e[x1 - 1][y1 - 1];
            else sideUPBox = 0;

            System.out.println(bigBox - rightBox - upBox + sideUPBox);
            
        }

        sc.close();

    }


}