Hướng giải của Tổng Lưới Con Lớn Nhất
Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.
Tác giả:
Hướng dẫn giải
Do kích thước trang trại nhỏ (\(N, M \le 100\)) và số truy vấn ít (\(Q \le 500\)):
- Ta sử dụng một cây BIT 2D để quản lý và cập nhật sản lượng tại từng ô đất.
- Với mỗi yêu cầu tìm kiếm vùng hình vuông kích thước \(K \times K\) có tổng sản lượng lớn nhất, ta duyệt qua tất cả các góc trên bên trái khả dĩ của hình vuông là \((i, j)\) sao cho \(1 \le i \le N - K + 1\) và \(1 \le j \le M - K + 1\).
- Tính tổng của vùng hình vuông này bằng BIT 2D trong \(O(\log N \log M)\) và cập nhật giá trị lớn nhất.
Độ phức tạp cho mỗi sự kiện loại 2: \(O(N \cdot M \cdot \log N \log M)\), tổng thể chạy rất nhanh dưới 0.1 giây.
Mã nguồn C++ mẫu
#include <bits/stdc++.h>
using namespace std;
int n, m, k, q;
vector<vector<long long>> bit;
void update(int x, int y, long long val) {
for (int i = x; i <= n; i += i & -i) {
for (int j = y; j <= m; j += j & -j) {
bit[i][j] += val;
}
}
}
long long query(int x, int y) {
long long s = 0;
for (int i = x; i > 0; i -= i & -i) {
for (int j = y; j > 0; j -= j & -j) {
s += bit[i][j];
}
}
return s;
}
long long range_query(int x1, int y1, int x2, int y2) {
return query(x2, y2) - query(x1 - 1, y2) - query(x2, y1 - 1) + query(x1 - 1, y1 - 1);
}
int main(){
ios_base::sync_with_stdio(false); cin.tie(NULL);
if (!(cin >> n >> m >> k >> q)) return 0;
bit.assign(n + 1, vector<long long>(m + 1, 0));
while (q--) {
int t; cin >> t;
if (t == 1) {
int x, y; long long val; cin >> x >> y >> val;
update(x, y, val);
} else {
long long max_sum = 0;
for (int i = 1; i + k - 1 <= n; i++) {
for (int j = 1; j + k - 1 <= m; j++) {
max_sum = max(max_sum, range_query(i, j, i + k - 1, j + k - 1));
}
}
cout << max_sum << "\n";
}
}
}
Nhận xét