Hướng dẫn cho Thao tác trên bảng (DHBB 2022)

Chỉ sử dụng khi thực sự cần thiết như một cách tôn trọng tác giả và người viết hướng dẫn này.

Chép code từ bài hướng dẫn để nộp bài là hành vi có thể dẫn đến khóa tài khoản.

Authors: kitsune

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:

C++

#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:

\[p_{i, \, j} = p_{i \, - \, 1, \, j} + p_{i, \, j \, - \, 1} - p_{i \, - \, 1, \, j \, - \, 1} + a_{i, \, j}\]

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:

\[\sum_{i \, = \, x}^{u} \sum_{j \, = \, y}^{v} a_{i, \, j} = p_{u, \, v} - p_{x \, - \, 1, \, v} - p_{u, \, y \, - \, 1} + p_{x \, - \, 1, \, y \, - \, 1}\]

Độ phức tạp: \(O(n \cdot m + Q)\).

Code tham khảo:

C++

#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:

C++

#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:

C++

#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:

C++

#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;
}

Bình luận

-3

nguyen_ducminh 3:48 p.m. 5 Tháng 7, 2023

ở 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\)