Hướng giải của Điều Khiển LED 2D

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.

Tác giả: kienadmin

Hướng dẫn giải

Bài toán yêu cầu thực hiện cập nhật đoạn 2D (cộng thêm \(val\) cho hình chữ nhật) và truy vấn tổng vùng hình chữ nhật. Tương tự như trường hợp 1D, ta phát triển công thức tích lũy 2D và cần duy trì 4 cây Fenwick Tree 2D:

  1. bit1 quản lý \(D[i][j]\).
  2. bit2 quản lý \(D[i][j] \cdot (i - 1)\).
  3. bit3 quản lý \(D[i][j] \cdot (j - 1)\).
  4. bit4 quản lý \(D[i][j] \cdot (i - 1) \cdot (j - 1)\).

Khi cập nhật một vùng hình chữ nhật \([x_1, y_1] \to [x_2, y_2]\), ta thực hiện cộng/trừ tương ứng tại 4 góc của ma trận sai phân.

Mã nguồn C++ mẫu

#include <bits/stdc++.h>
using namespace std;

int n, m, q;
vector<vector<long long>> bit1, bit2, bit3, bit4;

void update(vector<vector<long long>>& bit, 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;
        }
    }
}

void update_point(int x, int y, long long val) {
    update(bit1, x, y, val);
    update(bit2, x, y, val * (x - 1));
    update(bit3, x, y, val * (y - 1));
    update(bit4, x, y, val * (x - 1) * (y - 1));
}

void range_update(int x1, int y1, int x2, int y2, long long val) {
    update_point(x1, y1, val);
    update_point(x1, y2 + 1, -val);
    update_point(x2 + 1, y1, -val);
    update_point(x2 + 1, y2 + 1, val);
}

long long query(const vector<vector<long long>>& bit, 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 prefix_query(int x, int y) {
    return query(bit1, x, y) * x * y 
         - query(bit2, x, y) * y 
         - query(bit3, x, y) * x 
         + query(bit4, x, y);
}

long long range_query(int x1, int y1, int x2, int y2) {
    return prefix_query(x2, y2) - prefix_query(x1 - 1, y2) 
         - prefix_query(x2, y1 - 1) + prefix_query(x1 - 1, y1 - 1);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    if (!(cin >> n >> m >> q)) return 0;
    bit1.assign(n + 2, vector<long long>(m + 2, 0));
    bit2.assign(n + 2, vector<long long>(m + 2, 0));
    bit3.assign(n + 2, vector<long long>(m + 2, 0));
    bit4.assign(n + 2, vector<long long>(m + 2, 0));
    while (q--) {
        int t; cin >> t;
        if (t == 1) {
            int x1, y1, x2, y2; long long val; cin >> x1 >> y1 >> x2 >> y2 >> val;
            range_update(x1, y1, x2, y2, val);
        } else {
            int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
            cout << range_query(x1, y1, x2, y2) << "\n";
        }
    }
}

Nhận xét

Không có ý kiến tại thời điểm này.