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}$ 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:

#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

-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$