棋盘战车异或攻击(TOPOVI)

题目描述

这里有一个 $n\times n$ 的棋盘，棋盘上有 $k$ 个棋子，每个棋子有一个武力值 $w_i$。

我们做出如下规定：

• 一个棋子的攻击范围是它所在的这一行与这一列，不包括它自己。
• 一个棋盘上的单元格可以被攻击，当且仅当能攻击到它的所有棋子的武力值的异或和大于 $0$。

现在我们会进行 $p$ 次操作，请求出每次操作后会被攻击到的格子总数。

输入格式

第一行三个整数 $n,k,p$。

接下来 $k$ 行，一行三个整数 $x_i,y_i,w_i$，第 $i$ 行表示有一个棋子在 $(x_i,y_i)$ 的位置，武力值为 $w_i$。

接下来 $p$ 行，一行四个整数 $r_1,c_1,r_2,c_2$，表示将位于 $(r_1,c_1)$ 的棋子移至 $(r_2,c_2)$。

输出格式

共 $p$ 行，一行一个整数，第 $i$ 行表示第 $i$ 次操作后会被攻击到的格子总数。

样例输入 #1

2 2 2
1 1 1
2 2 1
2 2 2 1
1 1 1 2

样例输出 #1

4
0

样例输入 #2

2 2 2
1 1 1
2 2 2
2 2 2 1
1 1 1 2

样例输出 #2

4
2

样例输入 #3

3 3 4
1 1 1
2 2 2
2 3 3
2 3 3 3
3 3 3 1
1 1 1 2
3 1 3 2

样例输出 #3

6
7
7
9

数据范围

数据范围及限制

• 对于 $25\%$ 的数据，保证 $n,k\le 100$。
• 对于 $100\%$ 的数据，保证 $1\le n\le 10^9$，$1\le k\le 10^5$，$1\le p\le 10^5$，$1\le x_i,y_i,r_1,c_1,r_2,c_2\le n$，$1\le w_i\le 10^9$，在移动过程中棋子不会重叠。

说明

本题满分 $120$ 分。

本题译自 Croatian Open Competition in Informatics 2015/2016 Contest #1 T4 TOPOVI。

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1900。

测试点分布

出处：原题链接