Cho ma trận A (M x N) và Q truy vấn. Mỗi truy vấn (x1, y1, x2, y2) yêu cầu bạn tính trung bình cộng của tất cả các ô trong hình chữ nhật con từ (x1, y1) đến (x2, y2).

Gợi ý: Tổng = P[x2][y2] - .... Số lượng ô = (x2 - x1 + 1) * (y2 - y1 + 1). Trung bình = Tổng / Số lượng.

Input:

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

M dòng ma trận A (1 <= A[i][j] <= 1000).

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

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

Output:

Q dòng, mỗi dòng là kết quả trung bình. (In ra phần nguyên, ví dụ: 25.6 thì in 25).

Ví dụ:

Input:

2 2
10 20
30 40
1
1 1 2 2

Output:

25

(Giải thích: (10 + 20 + 30 + 40) / 4 = 25)

Đề bài: 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ử nhỏ nhất.

Input:

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

M dòng ma trận A (1 <= A[i][j] <= 1000).

Output:

In ra tổng nhỏ nhất tìm được.

Ví dụ:

Input:

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

Output:

11

(Giải thích: Hình vuông (2,2)-(3,3) là [1 7; 1 2] có tổng 11, nhỏ nhất)

Cho ma trận A (M x N) (chỉ chứa số không âm) và Q truy vấn. Mỗi truy vấn (x1, y1, x2, y2) hỏi xem hình chữ nhật con đó có chứa toàn số 0 hay không.

Gợi ý: Nếu tổng P-Sum của HCN đó bằng 0, thì nó chứa toàn số 0.

Input:

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

M dòng ma trận A (0 <= A[i][j] <= 1000).

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

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

Output:

Q dòng, mỗi dòng in "YES" (nếu tổng bằng 0) hoặc "NO" (nếu tổng > 0).

Ví dụ:

Input:

3 3
1 1 0
0 0 0
0 0 1
2
1 2 2 3
2 1 3 2

Output:

NO
YES

(Giải thích 1: HCN (1,2)-(2,3) [1 0; 0 0] có tổng 1. Giải thích 2: HCN (2,1)-(3,2) [0 0; 0 0] có tổng 0.)

Cho ma trận A (M x N) và Q truy vấn. Mỗi truy vấn gồm 8 số, mô tả 2 HCN (Rect1: x1, y1, x2, y2; Rect2: a1, b1, a2, b2). Hai HCN này có thể giao nhau. Tính tổng của tất cả các ô nằm trong Rect1 hoặc Rect2.

Gợi ý: Tổng(A hoặc B) = Tổng(A) + Tổng(B) - Tổng(Phần Giao). Bạn cần tìm tọa độ (xgiao, ygiao, ...) của phần giao nhau (nếu có) và trừ nó đi.

Input:

Dòng đầu M, N. Ma trận A.

Dòng tiếp theo Q.

Q dòng, mỗi dòng 8 số.

Output:

Q dòng, mỗi dòng là tổng hợp.

Ví dụ:

Input:

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

Output:

7

(Giải thích: Rect1 (1,1)-(2,2) tổng 4. Rect2 (2,2)-(3,3) tổng 4. Giao nhau (2,2)-(2,2) tổng 1. Kết quả = 4 + 4 - 1 = 7)

Cho ma trận A (M x N) chứa cả số âm và Q truy vấn. Mỗi truy vấn (x1, y1, x2, y2) yêu cầu đếm xem có bao nhiêu ô dương (A[i][j] > 0) trong HCN con.

Gợi ý: Tạo một ma trận phụ B kích thước M x N. B[i][j] = 1 nếu A[i][j] > 0, ngược lại B[i][j] = 0. Xây dựng P-Sum 2D trên ma trận B.

Input:

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

M dòng ma trận A (-1000 <= A[i][j] <= 1000).

Dòng tiếp theo chứa Q.

Q dòng truy vấn.

Output:

Q dòng, mỗi dòng là số lượng ô dương.

Ví dụ:

Input:

3 3
1 -2 3
0 5 -1
8 -9 2
1
1 1 2 3

Output:

3

(Giải thích: HCN (1,1)-(2,3) là [1 -2 3; 0 5 -1]. Có 3 số dương là 1, 3, 5)

Cho ma trận A (M x N) và Q truy vấn (x1, y1, x2, y2). Với mỗi truy vấn, hãy tính tổng của các ô trắng (i+j chẵn) nằm trong HCN con đó.

Gợi ý: Xây dựng mảng PSum PTrang. PTrang[i][j] chỉ cộng A[i][j] nếu (i+j) chẵn. Sau đó truy vấn trên PTrang.

Input:

Dòng đầu M, N. Ma trận A.

Dòng tiếp theo Q.

Q dòng truy vấn.

Output:

Q dòng, mỗi dòng là tổng ô trắng.

Ví dụ:

Input:

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

Output:

25

(Giải thích: Cả ma trận, ô trắng là 1, 3, 5, 7, 9. Tổng = 25)

Cho ma trận A (M x N), số K và một số Target T. Tìm hình vuông con KxK có tổng gần với T nhất (tức là abs(Tong - T) nhỏ nhất).

Gợi ý: Duyệt qua tất cả các hình vuông KxK, tính tổng S của chúng. Dùng một biến mindiff (khởi tạo Rất Lớn) và resultsum (tổng của HCN tốt nhất). Nếu abs(S - T) < mindiff thì cập nhật mindiff và result_sum.

Input:

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

Dòng tiếp theo chứa Target T.

M dòng ma trận A (1 <= A[i][j] <= 100).

Output:

In ra tổng của hình vuông KxK gần T nhất. (Nếu có nhiều tổng cách đều T, in ra tổng nhỏ hơn).

Ví dụ:

Input:

3 3 2
20
1 1 1
1 1 1
8 8 10

Output:

20

Cho ma trận A (M x N) và Q truy vấn. Mỗi truy vấn gồm 8 số, mô tả 2 HCN (Rect1: x1, y1, x2, y2; Rect2: a1, b1, a2, b2). In "A" nếu Tổng(Rect1) > Tổng(Rect2), "B" nếu Tổng(Rect2) > Tổng(Rect1), và "HOA" (Hòa) nếu bằng nhau.

Gợi ý: Dùng P-Sum tính sumA và sumB, sau đó so sánh.

Input:

Dòng đầu M, N. Ma trận A.

Dòng tiếp theo Q.

Q dòng, mỗi dòng 8 số.

Output:

Q dòng, mỗi dòng là "A", "B", hoặc "HOA".

Ví dụ:

Input:

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

Output:

B
HOA

(Giải thích 1: Tổng A (1,1) = 1. Tổng B (3,3) = 9. 1 < 9 -> B. Giải thích 2: Cả hai đều là cả ma trận -> tổng 45. 45 == 45 -> HOA)

Cho ma trận A (M x N) và Q truy vấn. Mỗi truy vấn gồm 2 số (r, c). Bạn cần tính tổng của tất cả các ô trên hàng r và tất cả các ô trên cột c.

Gợi ý: Tổng(Hàng r) + Tổng(Cột c) - A[r][c] (vì A[r][c] bị cộng 2 lần). Tổng(Hàng r) = P[r][N] - P[r-1][N]. Tổng(Cột c) = P[M][c] - P[M][c-1].

Input:

Dòng đầu M, N. Ma trận A.

Dòng tiếp theo Q.

Q dòng, mỗi dòng 2 số r, c.

Output:

Q dòng, mỗi dòng là tổng chữ thập.

Ví dụ:

Input:

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

Output:

25

(Giải thích: Hàng 2 (4+5+6)=15. Cột 2 (2+5+8)=15. A[2][2]=5. Kết quả = 15 + 15 - 5 = 25)

Cho ma trận A có kích thước chẵn M x N (M và N đều chẵn). Một đường cắt ngang ở M/2 và một đường cắt dọc ở N/2 sẽ chia ma trận làm 4 hình chữ nhật con (Góc Trên-Trái, Trên-Phải, Dưới-Trái, Dưới-Phải) đều có kích thước (M/2) x (N/2). Hãy in ra tổng của 4 HCN con này.

Gợi ý: Dùng P-Sum để tính 4 tổng:

(1, 1) -> (M/2, N/2)

(1, N/2 + 1) -> (M/2, N)

(M/2 + 1, 1) -> (M, N/2)

(M/2 + 1, N/2 + 1) -> (M, N)

Input:

Dòng đầu M, N (2 <= M, N <= 100, M và N chẵn).

M dòng ma trận A.

Output:

In ra 4 số là 4 tổng, theo thứ tự: Trên-Trái, Trên-Phải, Dưới-Trái, Dưới-Phải.

Ví dụ:

Input:

4 4
1 1 2 2
1 1 2 2
3 3 4 4
3 3 4 4

Output:

4
8
12
16