Editorial for Thao tác trên bảng (DHBB 2022)
Submitting an official solution before solving the problem yourself is a bannable offence.
Authors:
Subtask 1
Tag: brute-force.
Vì giới hạn đủ nhỏ nên ta có thể dùng hai vòng lặp (một vòng lặp từ x đến u, một vòng lặp từ y đến v) để thực hiện cả hai loại thao tác.
Độ phức tạp: O(Q \cdot n \cdot m).
Code tham khảo:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll a[501][501];
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, Q;
cin >> n >> m >> Q;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> a[i][j];
}
}
while (Q--) {
int t;
cin >> t;
if (t == 1) {
int x, y, u, v, w;
cin >> x >> y >> u >> v >> w;
for (int i = x; i <= u; i++) {
for (int j = y; j <= v; j++) {
a[i][j] += w;
}
}
} else {
int x, y, u, v;
cin >> x >> y >> u >> v;
ll ans = 0;
for (int i = x; i <= u; i++) {
for (int j = y; j <= v; j++) {
ans += a[i][j];
}
}
cout << ans << "\n";
}
}
return 0;
}
Subtask 2
Tag: prefix-sum.
Vì tất cả thao tác loại 1 xuất hiện trước các thao tác loại 2 nên ta có thể xử lý tất cả thao tác loại 1 hết rồi rồi trả lời từng thao tác loại 2 sau.
Trước hết, ta cần biết về tổng tiền tố trên bảng. Trên bảng a, gọi p_{i, \, j} là tổng giá trị của các ô nằm trong hình chữ nhật có ô ở góc trái trên là ô (1, 1) và ô ở góc phải dưới là ô (i, j). Khi đó p(i, j) là tổng tiền tố tại ô (i, j). Để tính p_{i, \, j}, ta có công thức:

Quay lại bài tập, để xứ lý tất cả thao tác loại 1, ta có thể làm như sau:
- Khởi tạo tất cả d_{i, \, j} bằng 0;
- Với mỗi thao tác loại 1, tăng d_{x, \, y} và d_{u \, + \, 1, \, v \, + \, 1} thêm w, giảm d_{x, \, v \, + \, 1} và d_{u \, + \, 1, \, y} đi w;
- Cuối cùng, thay tất cả d_{i, \, j} bằng tổng tiền tại ô (i, j) trên bảng d và tăng a_{i, \, j} thêm d_{i, \, j}.
Để xử lý các thao tác loại 2, ta cần tính trước bảng p với p_{i, \, j} là tổng tiền tố tại ô (i, j) trên bảng a. Sau đó, để tính tổng giá trị của các ô nằm trong hình chữ nhật có ô ở góc trái trên là ô (x, y) và ô ở góc phải dưới là ô (u, v), ta có công thức:

Độ phức tạp: O(n \cdot m + Q).
Code tham khảo:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct data {
int x, y, u, v, w;
data(int x, int y, int u, int v, int w) : x(x), y(y), u(u), v(v), w(w) {
}
data() {
}
};
int n, m;
ll a[501][501], p[501][501], d[502][502];
vector <data> upd;
void rebuild() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
d[i][j] = 0;
}
}
for (auto i : upd) {
d[i.x][i.y] += i.w;
d[i.x][i.v + 1] -= i.w;
d[i.u + 1][i.y] -= i.w;
d[i.u + 1][i.v + 1] += i.w;
}
upd.clear();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
d[i][j] += d[i - 1][j] + d[i][j - 1] - d[i - 1][j - 1];
a[i][j] += d[i][j];
p[i][j] = p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1] + a[i][j];
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int Q;
cin >> n >> m >> Q;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> a[i][j];
p[i][j] = p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1] + a[i][j];
}
}
int prv_t = 0;
while (Q--) {
int t;
cin >> t;
if (t == 1) {
int x, y, u, v, w;
cin >> x >> y >> u >> v >> w;
upd.push_back(data(x, y, u, v, w));
} else {
int x, y, u, v;
cin >> x >> y >> u >> v;
if (prv_t == 1) {
rebuild();
}
cout << p[u][v] - p[x - 1][v] - p[u][y - 1] + p[x - 1][y - 1] << "\n";
}
prv_t = t;
}
return 0;
}
Subtask 3
Tag: prefix-sum, math-general.
Ta lưu lại các thao tác loại 1 đã xuất hiện. Với mỗi thao tác loại 2, đáp án tạm thời là tổng giá trị của các ô nằm trong hình chữ nhật có ô ở góc trái trên là ô (x, y) và ô ở góc phải dưới là ô (u, v) trên bảng a ban đầu. Sau đó, ta sẽ duyệt qua các thao tác loại 1 đã lưu. Ta tìm s là diện tích phần giao giữa hình chữ nhật của thao tác 2 hiện tại và hình chữ nhật của thao tác 1 đang duyệt và tăng đáp án thêm s \cdot w.
Độ phức tạp: O(n \cdot m + Q ^ 2).
Code tham khảo:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct data {
int x, y, u, v, w;
data(int x, int y, int u, int v, int w) : x(x), y(y), u(u), v(v), w(w) {
}
data() {
}
};
int n, m;
ll a[501][501], p[501][501];
vector <data> upd;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int Q;
cin >> n >> m >> Q;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> a[i][j];
p[i][j] = p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1] + a[i][j];
}
}
while (Q--) {
int t;
cin >> t;
if (t == 1) {
int x, y, u, v, w;
cin >> x >> y >> u >> v >> w;
upd.push_back(data(x, y, u, v, w));
} else {
int x, y, u, v;
cin >> x >> y >> u >> v;
ll ans = p[u][v] - p[x - 1][v] - p[u][y - 1] + p[x - 1][y - 1];
for (auto i : upd) {
i.x = max(i.x, x);
i.y = max(i.y, y);
i.u = min(i.u, u);
i.v = min(i.v, v);
if (i.x > i.u || i.y > i.v) {
continue;
}
ans += (i.u - i.x + 1) * (i.v - i.y + 1) * (ll)i.w;
}
cout << ans << "\n";
}
}
return 0;
}
Subtask 4 (cách 1)
Tag: sqrt-time, prefix-sum, math-general.
Cách này kết hợp subtask 2 và subtask 3 nhưng thêm một thứ nho nhỏ là sau B thao tác, ta sẽ gọi hàm rebuild
một lần. Tuy là nhỏ nhưng nó cải thiện độ phức tạp rất nhiều.
Theo lý thuyết, để tìm được B tốt nhất, ta sẽ xem xét số lượng phép tính của cả các loại thao tác tính theo n, m, Q và B.
- Tất cả các lần gọi hàm
rebuild
tốn \displaystyle \frac{Q}{B} \cdot (B + n \cdot m) phép tính. - Tất cả các lần thực hiện thao tác loại 1 tốn Q phép tính.
- Tất cả các lần thực hiện thao tác loại 2 tốn Q \cdot B phép tính.
Ta sẽ tìm B sao cho số lượng phép tính của các loại thao tác có B là bằng nhau, tức là:
\displaystyle \frac{Q}{B} \cdot (B + n \cdot m) = Q \cdot B
\Leftrightarrow Q \cdot B ^ 2 - B - Q \cdot n \cdot m = 0.
Thay n, m và Q bởi các giới hạn đề cho, ta sẽ giải phương trình trên và có được một nghiệm dương là B \approx 500.
Nhưng thực tế thì không giống với lý thuyết. Tuy B = 500 là đủ nhanh để AC bài này nhưng ta có thể thử B với các giá trị gần với 500 như 400, 600, 700, 800... và chọn ra B chạy với thời gian nhanh nhất. Ở đây ta có thể chọn B = 700.
Độ phức tạp: \displaystyle O\left(\left(B + \frac{Q}{B}\right) \cdot (n \cdot m + Q)\right).
Code tham khảo:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int B = 700;
struct data {
int x, y, u, v, w;
data(int x, int y, int u, int v, int w) : x(x), y(y), u(u), v(v), w(w) {
}
data() {
}
};
int n, m;
ll a[501][501], p[501][501], d[502][502];
vector <data> upd;
void rebuild() {
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
d[i][j] = 0;
}
}
for (auto i : upd) {
d[i.x][i.y] += i.w;
d[i.x][i.v + 1] -= i.w;
d[i.u + 1][i.y] -= i.w;
d[i.u + 1][i.v + 1] += i.w;
}
upd.clear();
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
d[i][j] += d[i - 1][j] + d[i][j - 1] - d[i - 1][j - 1];
a[i][j] += d[i][j];
p[i][j] = p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1] + a[i][j];
}
}
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int Q;
cin >> n >> m >> Q;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
cin >> a[i][j];
p[i][j] = p[i - 1][j] + p[i][j - 1] - p[i - 1][j - 1] + a[i][j];
}
}
while (Q--) {
if (Q % B == 0) {
rebuild();
}
int t;
cin >> t;
if (t == 1) {
int x, y, u, v, w;
cin >> x >> y >> u >> v >> w;
upd.push_back(data(x, y, u, v, w));
} else {
int x, y, u, v;
cin >> x >> y >> u >> v;
ll ans = p[u][v] - p[x - 1][v] - p[u][y - 1] + p[x - 1][y - 1];
for (auto i : upd) {
i.x = max(i.x, x);
i.y = max(i.y, y);
i.u = min(i.u, u);
i.v = min(i.v, v);
if (i.x > i.u || i.y > i.v) {
continue;
}
ans += (i.u - i.x + 1) * (i.v - i.y + 1) * (ll)i.w;
}
cout << ans << "\n";
}
}
return 0;
}
Subtask 4 (cách 2)
Tag: bit2d, prefix-sum, math-general.
Các bạn có thể tham khảo cách làm này tại đây.
Độ phức tạp: O((n \cdot m + Q) \cdot \log n \cdot \log m).
Code tham khảo:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int n, m;
ll tree[501][501][4];
void update(int x, int y, int w) {
for (int i = x; i <= n; i += i & (-i)) {
for (int j = y; j <= m; j += j & (-j)) {
tree[i][j][0] += w;
tree[i][j][1] += x * (ll)w;
tree[i][j][2] += y * (ll)w;
tree[i][j][3] += x * y * (ll)w;
}
}
}
void update(int x, int y, int u, int v, int w) {
update(x, y, w);
update(x, v + 1, -w);
update(u + 1, y, -w);
update(u + 1, v + 1, w);
}
ll query(int x, int y) {
ll ans = 0;
for (int i = x; i > 0; i -= i & (-i)) {
for (int j = y; j > 0; j -= j & (-j)) {
ans += (x + 1) * (y + 1) * tree[i][j][0] - (y + 1) * tree[i][j][1] - (x + 1) * tree[i][j][2] + tree[i][j][3];
}
}
return ans;
}
ll query(int x, int y, int u, int v) {
return query(u, v) - query(x - 1, v) - query(u, y - 1) + query(x - 1, y - 1);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int Q;
cin >> n >> m >> Q;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= m; j++) {
int a;
cin >> a;
update(i, j, i, j, a);
}
}
while (Q--) {
int t;
cin >> t;
if (t == 1) {
int x, y, u, v, w;
cin >> x >> y >> u >> v >> w;
update(x, y, u, v, w);
} else {
int x, y, u, v;
cin >> x >> y >> u >> v;
cout << query(x, y, u, v) << "\n";
}
}
return 0;
}
Comments
ở sub 4 cách 1 đoạn biến đổi phương trình hình như bị sai
mình nghĩ phải là:
Q \cdot B^2 - Q \cdot B - Q \cdot m \cdot n = 0