Đọc R, C và ma trận A R*C. Tính prefix sum 2D: P[i][j] = tổng các A[r][c] với 0 <= r <= i và 0 <= c <= j. Sau đó đọc Q truy vấn, mỗi truy vấn 4 số r1 c1 r2 c2 (0-based, inclusive). In tổng vùng con của A trên một dòng cho mỗi truy vấn. Công thức: S = P[r2][c2] - (r1>0?P[r1-1][c2]:0) - (c1>0?P[r2][c1-1]:0) + (r1>0 && c1>0?P[r1-1][c1-1]:0).
Dòng 1: R C. R dòng ma trận. Dòng kế: Q. Q dòng truy vấn.
1 <= R, C <= 200; 1 <= Q <= 1000
Q dòng tổng vùng con.
Ví dụ:
Đầu vào:
3 3
1 2 3
4 5 6
7 8 9
2
0 0 2 2
1 1 2 2
Đầu ra:
45
28
Giải thích:
Đang tải editor...