问题分析

本题的核心是计算棋盘上被攻击的格子总数，其中格子被攻击的条件是：所有能攻击到该格子的棋子的武力值异或和大于0。棋子的攻击方式与中国象棋的“车”相同，即能攻击同一行和同一列的所有格子。

关键观察：对于格子 $(x, y)$，能攻击到它的棋子是第 $x$ 行的所有棋子和第 $y$ 列的所有棋子。设第 $x$ 行所有棋子的武力值异或和为 $rxor[x]$，第 $y$ 列所有棋子的武力值异或和为 $cxor[y]$，则该格子的总攻击异或和为 $rxor[x] \oplus cxor[y]$。因此，格子 $(x, y)$ 被攻击的条件等价于 $rxor[x] \oplus cxor[y] \neq 0$（即 $rxor[x] \neq cxor[y]$）。

核心思路

1. 总数转换：总格子数为 $n^2$，被攻击的格子数 = 总格子数 - 不被攻击的格子数（即 $rxor[x] = cxor[y]$ 的格子数）。
2. 计数维护：用 $rcnt[v]$ 表示异或和为 $v$ 的行数，$ccnt[v]$ 表示异或和为 $v$ 的列数。则不被攻击的格子数为 $\sum (rcnt[v] \times ccnt[v])$（对所有可能的 $v$ 求和）。
3. 动态更新：每次移动棋子时，需更新棋子原位置和新位置的行、列异或和（$rxor$ 和 $cxor$），并同步调整 $rcnt$ 和 $ccnt$ 的计数，进而更新不被攻击的格子数，最终得到被攻击的格子数。

算法流程

1. 初始化：初始时无棋子，所有行和列的异或和均为0，因此 $rcnt[0] = n$，$ccnt[0] = n$，初始不被攻击的格子数为 $n \times n$。
2. 添加/移除棋子：
   • 移除棋子时，对原行 $r$ 和原列 $c$，将其异或和更新（异或棋子的武力值），并调整 $rcnt$ 和 $ccnt$ 中对应值的计数。
   • 添加棋子时，对新行 $r$ 和新列 $c$，执行与移除类似的操作（异或运算具有可逆性，添加等价于再次异或该武力值）。
3. 计算答案：每次操作后，被攻击的格子数为 $n^2 - \sum (rcnt[v] \times ccnt[v])$。

算法标签

哈希表 异或运算 动态维护 计数统计