棋盘战车异或攻击(TOPOVI) 题解

思路分析

按题目要求使用对应数据结构与算法模拟/递推求解，注意数据范围边界与时间复杂度。

参考代码

#include <cstdint>
#include <iostream>
#include <map>
#include <unordered_map>
#include <utility>
using namespace std;

struct PairHash {
    size_t operator()(const pair<int, int>& p) const {
        return ((uint64_t)p.first << 32) ^ (uint32_t)p.second;
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    long long n;
    int k, p;
    if (!(cin >> n >> k >> p)) return 0;

    unordered_map<int, int> row_xor, col_xor;
    unordered_map<int, long long> cnt_r, cnt_c;
    unordered_map<pair<int, int>, int, PairHash> piece;
    row_xor.reserve(k * 2 + p * 2);
    col_xor.reserve(k * 2 + p * 2);
    cnt_r.reserve(k * 2 + p * 2);
    cnt_c.reserve(k * 2 + p * 2);
    piece.reserve(k * 2);

    cnt_r[0] = n;
    cnt_c[0] = n;
    long long same_pairs = n * n;

    auto xor_row = [&](int r, int w) {
        int old_v = row_xor[r];
        int new_v = old_v ^ w;
        same_pairs -= cnt_c[old_v];
        cnt_r[old_v]--;
        row_xor[r] = new_v;
        cnt_r[new_v]++;
        same_pairs += cnt_c[new_v];
    };

    auto xor_col = [&](int c, int w) {
        int old_v = col_xor[c];
        int new_v = old_v ^ w;
        same_pairs -= cnt_r[old_v];
        cnt_c[old_v]--;
        col_xor[c] = new_v;
        cnt_c[new_v]++;
        same_pairs += cnt_r[new_v];
    };

    for (int i = 0; i < k; ++i) {
        int r, c, w;
        cin >> r >> c >> w;
        piece[{r, c}] = w;
        xor_row(r, w);
        xor_col(c, w);
    }

    for (int i = 0; i < p; ++i) {
        int r1, c1, r2, c2;
        cin >> r1 >> c1 >> r2 >> c2;
        auto it = piece.find({r1, c1});
        int w = it->second;
        piece.erase(it);
        piece[{r2, c2}] = w;
        xor_row(r1, w);
        xor_col(c1, w);
        xor_row(r2, w);
        xor_col(c2, w);
        cout << (n * n - same_pairs) << "\n";
    }
    return 0;
}