Bạn được cho một ma trận (bảng) A kích thước M x N. Sau đó, bạn sẽ nhận được Q truy vấn. Mỗi truy vấn gồm 4 số nguyên x1, y1, x2, y2, đại diện cho tọa độ góc trên trái (x1, y1) và góc dưới phải (x2, y2) của một hình chữ nhật con.

Với mỗi truy vấn, nhiệm vụ của bạn là tính và in ra tổng của tất cả các ô A[i][j] nằm trong hình chữ nhật con đó (với x1 <= i <= x2 và y1 <= j <= y2).

Gợi ý: Nếu tính tổng bằng 2 vòng for lồng nhau cho mỗi truy vấn, thuật toán sẽ có độ phức tạp O(Q.M.N) và chắc chắn sẽ bị "Chạy quá thời gian".

Thay vào đó, hãy sử dụng Mảng Cộng Dồn 2 Chiều.

Xây dựng (O(M.N)): Tạo một ma trận P kích thước (M+1) x (N+1). P[i][j] = Tổng của tất cả các ô trong hình chữ nhật từ (1, 1) đến (i, j). Công thức xây dựng P: P[i][j] = A[i][j] + P[i-1][j] + P[i][j-1] - P[i-1][j-1]

Truy vấn (O(1)): Với mỗi truy vấn (x1, y1, x2, y2), tổng của hình chữ nhật con được tính bằng công thức (dựa trên nguyên lý bù trừ): Tong = P[x2][y2] - P[x1-1][y2] - P[x2][y1-1] + P[x1-1][y1-1]

Input:

Dòng đầu tiên chứa 2 số nguyên M, N.

M dòng tiếp theo, mỗi dòng chứa N số nguyên A[i][j], là các giá trị của ma trận.

Dòng tiếp theo chứa số nguyên Q.

Q dòng tiếp theo, mỗi dòng chứa 4 số nguyên x1, y1, x2, y2.

Output:

In ra Q dòng, mỗi dòng là kết quả (tổng) cho một truy vấn tương ứng.

Ràng buộc:

1 <= M, N <= 1000

1 <= Q <= 100000

-1000 <= A[i][j] <= 1000

1 <= x1 <= x2 <= M

1 <= y1 <= y2 <= N

(Tổng của một truy vấn có thể lớn, nên dùng long long để lưu mảng P và kết quả)

Ví dụ 1:

Input:

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

Output:

14
20

Tèo hiện tại đã bỏ làm lập trình viên và trở về về lquê trồng rau nuôi cá, anh ta có một mảnh vườn hình chữ nhật có kích thước NxM. Anh ta chia vườn của mình thành NxM ô vuông và trồng vào đó một cây cà rốt, tới vụ thu hoạch có những cây cà rốt bị chết và có những cây cà rốt có củ, anh ta muốn biết với mỗi mảnh vườn hình chữ nhật bắt đầu từ hàng x1 tới hàng x2 và từ cột y1 tới cột y2 thì số cà rốt thu hoạch được là bao nhiêu.

Biết rằng mảnh vườn được mô tả bởi một ma trận nhị phần, 0 tương ứng với cây cà rốt chết và 1 tương ứng với cây cà rốt có củ.

Định dạng đầu vào:

Dòng 1 là N và M

N dòng tiếp theo mỗi dòng M số mô tả mảnh vườn

Dòng tiếp theo là Q : số lượng truy vẫn

Q dòng tiếp theo mỗi dòng gồm 4 số: x1, x2, y1, y2 (trong đó x1, y1 là tọa độ điểm đầu; x2 và y2 là tọa độ điểm cuối)

Ràng buộc: 1<=N,M<=1000

Input:

8 8
1 1 0 0 0 1 1 1
1 0 0 0 1 1 1 1
0 1 1 1 0 0 1 0
1 1 1 1 0 1 1 0
1 1 1 1 1 0 1 1
1 0 0 1 0 1 0 1
0 0 0 0 1 0 1 0
1 1 0 0 0 1 0 1
3
2 3 1 7
2 2 2 7
1 2 1 8

Output:

8
3
10

Cho một bàn cờ vua kích thước n * n, trên mỗi ô của bàn cờ có ghi một con số. Biết ô trên trái của bàn cờ vua là ô trắng (các ô của bàn cờ vua có dạng xen kẽ trắng đen). Các cột được đánh số từ 1 đến n từ trái sang phải, các hàng được đánh số từ 1 đến n từ trên xuống dưới. Ô ở hàng i, cột j của bàn cờ được ký hiệu là ô (i, j).

Tý đưa ra những câu đố cho Tèo như sau: Tý sẽ cho Tèo biết các vùng hình chữ nhật trên bàn cờ, nhiệm vụ của Tèo là phải tính giá trị tuyệt đối của độ chênh lệch giữa tổng giá trị các ô trắng và tổng giá trị các ô đen trên vùng hình chữ nhật đó. Bạn hãy lập trình giúp Tèo trả lời các câu đố của Tý nhé.

Đầu vào:

Dòng đầu chứa số nguyên dương n (1 ≤ n ≤ 500)

n dòng tiếp theo, dòng thứ i chứa n số nguyên dương ai1, ai2,..., ain là các số ghi trên hàng i của bàn cờ (từ trái sang phải), mỗi số cách nhau một dấu cách (0 ≤ aij ≤ 100)

Dòng tiếp theo ghi số nguyên dương q là số câu hỏi (1 ≤ q ≤ 10000)

q dòng tiếp theo, mỗi dòng chứa bốn số nguyên dương r1, c1, r2, c2 là tọa độ hai đỉnh trên trái và dưới phải của một câu hỏi, mỗi số cách nhau một dấu cách (1 ≤ r1 ≤ r2 ≤ n, 1 ≤ c1 ≤ c2 <n).</p>

Đầu ra: Gồm g dòng, mỗi dòng chứa một số nguyên không âm là các câu trả lời cho q câu hỏi (theo đúng thứ tự câu hỏi).

Input:

3
1 3 5 
2 4 6 
0 10 5 
2 
1 1 2 2 
1 2 3 3

Output:

0
5

Cho ma trận A (M x N) và Q truy vấn. Mỗi truy vấn gồm 1 số k và 1 ký tự c:

Nếu c = 'R', tính tổng hàng k.

Nếu c = 'C', tính tổng cột k.

Gợi ý: Sau khi xây dựng P-Sum, Tổng(Hàng k) = P[k][N] - P[k-1][N].

Input:

Dòng đầu M, N (1 <= M, N <= 500).

M dòng ma trận A.

Dòng tiếp theo chứa Q (1 <= Q <= 10000).

Q dòng, mỗi dòng chứa k và c.

Output:

Q dòng, mỗi dòng là kết quả truy vấn.

Ví dụ:

Input:

3 3
1 2 3
4 5 6
7 8 9
2
2 R
3 C

Output:

15
18

Cho ma trận A (M x N) và Q truy vấn (x1, y1, x2, y2). Tính tổng của các ô nằm trên viền của hình chữ nhật con (x1, y1) đến (x2, y2).

Gợi ý: Tổng(Viền) = Tổng(HCN Lớn) - Tổng(HCN Lõi).

Input:

Dòng đầu M, N (1 <= M, N <= 500).

M dòng ma trận A.

Dòng tiếp theo chứa Q (1 <= Q <= 10000).

Q dòng truy vấn (x1, y1, x2, y2). (Đảm bảo x1 < x2, y1 < y2).

Output:

Q dòng, mỗi dòng là tổng viền.

Ví dụ:

Input:

4 4
1 1 1 1
1 2 2 1
1 2 2 1
1 1 1 1
1
1 1 4 4

Output:

12

(Giải thích: HCN lớn 4x4 (tổng 20) - HCN lõi 2x2 (tổng 8) = 12)

Cho ma trận A (M x N). Ô (i, j) là ô trắng nếu (i+j) chẵn, là ô đen nếu (i+j) lẻ. Tính tổng tất cả các ô trắng và tổng tất cả các ô đen trong ma trận.

Gợi ý: Xây dựng 2 mảng P-Sum: PTrang và PDen.

Input:

Dòng đầu M, N (1 <= M, N <= 100).

M dòng ma trận A.

Output:

Dòng 1: Tổng các ô trắng.

Dòng 2: Tổng các ô đen.

Ví dụ:

Input:

3 3
1 2 3
4 5 6
7 8 9

Output:

25
20

(Giải thích: Trắng = {1, 3, 5, 7, 9} -> Tổng 25. Đen = {2, 4, 6, 8} -> Tổng 20)

Cho ma trận A (M x N) và số K. Tìm hình vuông con kích thước K x K có tổng các phần tử lớn nhất.

Gợi ý: Duyệt qua tất cả các ô (i, j) có thể là góc dưới phải của hình vuông (từ i=K đến M, j=K đến N) và dùng P-Sum để tính tổng KxK kết thúc tại (i, j).

Input:

Dòng đầu M, N, K (1 <= K <= M, N <= 500).

M dòng ma trận A.

Output:

In ra tổng lớn nhất tìm được.

Ví dụ:

Input:

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

Output:

22

(Giải thích: Hình vuông (1,3)-(2,4) [3 4; 7 8] có tổng 22)

Cho ma trận A (M x N) và Q truy vấn. Mỗi truy vấn (x1, y1, x2, y2, X) yêu cầu đếm số lần giá trị X xuất hiện trong HCN con (x1, y1) đến (x2, y2).

Gợi ý: Xây dựng mảng P-Sum với P[i][j] = số lần X xuất hiện từ (1,1) đến (i,j).

Ràng buộc: Ma trận A chỉ chứa các số từ 0 đến 9.

Input:

Dòng đầu M, N (1 <= M, N <= 100).

M dòng ma trận A.

Dòng tiếp theo chứa Q (1 <= Q <= 1000).

Q dòng truy vấn (x1, y1, x2, y2, X).

Output:

Q dòng, mỗi dòng là số lượng đếm được.

Ví dụ:

Input:

3 3
1 2 1
2 1 2
1 2 1
2
1 1 3 3 1
1 1 2 2 2

Output:

5
2

Cho ma trận nhị phân (chỉ chứa 0 và 1) kích thước M x N, và số K. Đếm xem có bao nhiêu hình vuông con kích thước K x K chỉ chứa toàn số 1.

Gợi ý: Một hình vuông KxK toàn số 1 nếu tổng P-Sum của nó bằng K*K.

Input:

Dòng đầu M, N, K (1 <= K <= M, N <= 500).

M dòng ma trận A.

Output:

Số lượng hình vuông KxK toàn số 1.

Ví dụ:

Input:

4 4 2
1 1 0 1
1 1 1 0
0 1 1 1
1 1 1 1

Output:

4

Cho ma trận A (M x N). Tìm một đường cắt ngang (giữa hàng r và hàng r+1) sao cho chênh lệch (trị tuyệt đối của hiệu) giữa tổng các ô ở trên đường cắt (hàng 1..r) và tổng các ô ở dưới (hàng r+1..N) là nhỏ nhất.

Input:

Dòng đầu M, N (2 <= M, N <= 100).

M dòng ma trận A.

Output:

Giá trị chênh lệch nhỏ nhất.

Ví dụ:

Input:

3 3
1 1 1
1 1 1
10 10 10

Output:

24

(Giải thích: Cắt r=1: |3 - 33| = 30. Cắt r=2: |6 - 30| = 24. Nhỏ nhất là 24)

Tương tự như bài chia đôi ma trận theo chiều ngang, nhưng tìm đường cắt dọc (giữa cột c và c+1) sao cho chênh lệch tổng Trái và Phải là nhỏ nhất.

Input:

Dòng đầu M, N (2 <= M, N <= 100).

M dòng ma trận A.

Output:

Giá trị chênh lệch nhỏ nhất.

Ví dụ:

Input:

3 3
1 5 1
1 5 1
1 5 1

Output:

15