Hướng giải của Tổng XOR Vùng Hình Chữ Nhật

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

Phép toán XOR tự nghịch đảo (\(A \oplus A = 0\)). Do đó, nguyên lý Bao hàm - Loại trừ có thể áp dụng trực tiếp cho phép toán XOR thay vì phép cộng thông thường.

  1. Update: update(x, y, val) thực hiện XOR giá trị mới val vào bit[i][j] dọc theo các nút cha của ô \((x, y)\) trong BIT 2D.
  2. Query: Tính phép XOR tổng hợp của vùng chữ nhật từ \((x_1, y_1)\) đến \((x_2, y_2)\) bằng cách XOR: \[\text{ans} = Q(x_2, y_2) \oplus Q(x_1-1, y_2) \oplus Q(x_2, y_1-1) \oplus Q(x_1-1, y_1-1)\]

Mã nguồn C++ mẫu

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

int n, m, q;
vector<vector<long long>> bit;

void update(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;
        }
    }
}

long long query(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;
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    if (!(cin >> n >> m >> q)) return 0;
    bit.assign(n + 1, vector<long long>(m + 1, 0));
    while (q--) {
        int t; cin >> t;
        if (t == 1) {
            int x, y; long long val; cin >> x >> y >> val;
            update(x, y, val);
        } else {
            int x1, y1, x2, y2; cin >> x1 >> y1 >> x2 >> y2;
            cout << (query(x2, y2) ^ query(x1 - 1, y2) ^ query(x2, y1 - 1) ^ query(x1 - 1, y1 - 1)) << "\n";
        }
    }
}

Nhận xét

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