Tổng trên ma trận
Xem dạng PDF
Gửi bài giải
Điểm:
15,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Input:
stdin
Output:
stdout
Dạng bài
Ngôn ngữ cho phép
C, C++, Java, Kotlin, Pascal, PyPy, Python, Scratch
Cho mảng ~a~ kích thước ~m × n~ chứa các số nguyên.
Yêu cầu
Tính tổng các số trong hình chữ nhật có ô trái trên là ~(x, y)~ và ô phải dưới là ~(u, v)~.
Input
- Dòng đầu tiên là hai số ~m, n~.
- ~m~ dòng tiếp theo, dòng thứ ~i~ chứa ~n~ số nguyên là ~a[i][j]~.
- Dòng tiếp theo là số ~q~.
- ~q~ dòng tiếp theo, dòng thứ ~i~ chứa 4 số nguyên ~x, y, u, v~.
Output
- ~q~ dòng, dòng thứ ~i~ là câu trả lời cho truy vấn thứ ~i~.
Giới hạn:
- ~1 ≤ m, n ≤ 10^5~.
- ~1 ≤ m × n ≤ 10^5~.
- ~0 ≤ a[i][j] ≤ 100~.
- ~1 ≤ q ≤ 10~.
- ~1 ≤ x ≤ u ≤ m~.
- ~1 ≤ y ≤ v ≤ n~.
Sample Input
4 2
2 2
3 0
0 1
4 6
2
1 1 2 2
1 2 4 2
Sample Output
7
9
Bình luận
include <iostream>
include <vector>
using namespace std;
int main() { int m, n; cin >> m >> n; vector a(m+1, vector<int>(n+1, 0));
for(int i = 1; i <= m; i++) {
for(int j = 1; j <= n; j++) {
cin >> a[i][j];
}
}
vector<vector> prefix(m+1, vector<long long>(n+1, 0));
for(int i = 1; i <= m; i++) {
for(int j = 1; j <= n; j++) {
prefix[i][j] = a[i][j] + prefix[i-1][j] + prefix[i][j-1] - prefix[i-1][j-1];
}
}
int q;
cin >> q;
while(q--) {
int x, y, u, v;
cin >> x >> y >> u >> v;
long long res = prefix[u][v] - prefix[x-1][v] - prefix[u][y-1] + prefix[x-1][y-1];
cout << res << "\n";
}
return 0;
}
.