Editorial for Thao tác trên bảng (DHBB 2022)


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.

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:

#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}d_{u \, + \, 1, \, v \, + \, 1} thêm w, giảm d_{x, \, v \, + \, 1}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:

#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, QB.

  • 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, mQ 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


  • -3
    nguyen_ducminh 3:48 p.m. 5 jul, 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