Đề bài chuẩn DMOJ

Bài toán: Tìm tổng giá trị phần thưởng (Nguồn: Đề thi chính thức K10 và 11 DHBB 2015-2016)

Đề bài

Hiếu đang tham gia một cuộc thi kiến thức với phần thưởng được đặt trên một bảng hình chữ nhật kích thước ~ m \times n ~ (m hàng và n cột). Ô ở hàng thứ ~ i ~ và cột thứ ~ j ~ chứa giá trị phần thưởng ~ a_{ij} ~.

Hiếu sẽ nhận được yêu cầu dưới dạng ~ q ~ truy vấn. Mỗi truy vấn cung cấp hai cặp tọa độ ~ (y_k, x_k) ~ và ~ (v_k, u_k) ~, tương ứng với góc trên bên trái và góc dưới bên phải của một hình chữ nhật con trên bảng. Nhiệm vụ của bạn là tính tổng tất cả các giá trị phần thưởng trong hình chữ nhật con này.

Dữ liệu vào

• Dòng đầu tiên chứa ba số nguyên ~ m, n, q ~ (~ 1 \leq m, n \leq 10^3 ~, ~ 1 \leq q \leq 10^5 ~).
• ~ m ~ dòng tiếp theo, mỗi dòng chứa ~ n ~ số nguyên ~ a_{ij} ~ (~ |a_{ij}| \leq 10^6 ~).
• ~ q ~ dòng tiếp theo, mỗi dòng chứa bốn số nguyên ~ y_k, x_k, v_k, u_k ~ (~ 1 \leq y_k \leq v_k \leq m ~, ~ 1 \leq x_k \leq u_k \leq n ~).

Dữ liệu ra

• Ghi ra ~ q ~ dòng, mỗi dòng chứa một số nguyên là kết quả của truy vấn tương ứng.

Ví dụ

Dữ liệu vào

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

Dữ liệu ra

7
9

Giới hạn

• ~ 25\% ~ số test: ~ m, n \leq 50 ~.
• ~ 25\% ~ số test: ~ m, n \leq 1000 ~.
• ~ 50\% ~ số test còn lại: ~ m, n \leq 10^3 ~, ~ q \leq 10^5 ~.