P6532 [COCI2015-2016#1] TOPOVI 题解

· · 题解

题目链接

题意解释

“棋子的攻击方式与中国象棋里的車的攻击方式无异。”的意思是，一个棋子的攻击范围是它所在的这一行与这一列，不包括它自己。（这一点有亿些迷惑）

题目分析

看到异或，必须很敏感地想到 一个数 异或 他自己 等于 0，在这道题目中相当于没异或。

进而可以想到：一个单元格所受到攻击会等于这一行的异或和 异或 这一列的异或和，无需考虑这个单元格是否有棋子，棋子是否会攻击自己。因为无论是单元格还是棋子，都会异或两次，相当于没异或。

这样一来，每次放棋子就是在那个格子上异或棋子的武力值，每次移动棋子就是在棋子原来的位置再次异或这个棋子，并在移动的目标位置异或这个棋子。每次操作都可以转换为放棋子的操作了捏。

对于每一次修改答案，求会被攻击到的格子数，就是求总格子数减掉不会被攻击到的格子数。询问有后效性，故每一次的结果可以递推：上一次询问的结果 - 这一次移动格子所减少的被攻击的 + 这一次移动所增加的被攻击的。

怎样求增加或减少被攻击的格子数捏？

考虑每一个格子会给这一行和这一列带来影响，可以开个桶，按每行每列分开统计有多少个。每一次操作，修改该行和该列原来的桶，修改异或值，修改新的异或值的桶。

总的梳理一下思路。对于每次操作：

这样，每次操作可以 O(1) 解决了！

注意

\texttt{AC Code}

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

int n, k, q;
long long ans;
unordered_map < int, int > rcnt, ccnt, rxor, cxor;
map < pair < int, int > , int > rook;
  // rcnt 和 ccnt 是桶
  // rxor 和 cxor 表示行和列的异或和
  // rook 表示棋盘

void move(int _r, int _c, int _v) { // 减去减少的，加上增加的，就是改变量
    ans = ans - (n - ccnt[rxor[_r]]) - (n - rcnt[cxor[_c]]);
  // 因为第 r 行增加一个棋子，原来与第 r 行相交的能被控制的格子现在不能了，需要减去原来能控制的数目
    if (rxor[_r] != cxor[_c]) ++ans;// 所在格子如果原来是被控制的，则多减去一次，需要加回来

    --rcnt[rxor[_r]], rcnt[rxor[_r] ^= _v]++;
    --ccnt[cxor[_c]], ccnt[cxor[_c] ^= _v]++;

    ans = ans + (n - ccnt[rxor[_r]]) + (n - rcnt[cxor[_c]]);
  // 更新以后，新增加控制的要加上
    if (rxor[_r] != cxor[_c]) --ans; // 加多了要减
    rook[make_pair(_r, _c)] ^= _v;
}

int main() {
    scanf("%d%d%d", &n, &k, &q);
    rcnt[0] = ccnt[0] = n;
    for (int i = 1, _r, _c, _v; i <= k; ++i) {
        scanf("%d%d%d", &_r, &_c, &_v);
        move(_r, _c, _v);
    }
    int _r1, _r2, _c1, _c2, rov;
    while (q--) {
        scanf("%d%d%d%d", &_r1, &_c1, &_r2, &_c2);
        rov = rook[make_pair(_r1, _c1)];
        move(_r1, _c1, rov);
        move(_r2, _c2, rov);
        printf("%lld\n", ans);
    }
    return 0;
}

最后，祝 CSP2022 RP++！