自动搬运

查看原文

来自洛谷，原作者为

	Orange_qwq 废物

搬运于2025-08-24 22:21:39，当前版本为作者最后更新于2022-10-07 23:15:54，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题目链接

题意解释

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

题目分析

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

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

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

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

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

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

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

• 放置棋子
• 修改桶的值
• 修改答案

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

注意

• 此题储存答案的变量需要开 ll。

• 数据较大，需要离散化，也可以用 map 或 unordered_map 解决。

• map 时间复杂度较大，需要用 unordered_map，也可以加快读。

$\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++！