[AdditionalFile5597.zip](file://AdditionalFile5597.zip?type=additional_file)

#5597. 「USACO 2026 First Platinum」Pluses and Minuses

标签: 传统 | 时间限制: 2000 ms | 内存限制: 256 MiB |

题目描述

题目译自 USACO 2026 First Contest, Platinum Problem 3. Pluses and Minuses

农夫约翰曾经在他的牧场地上画了一个矩形网格。在每个格子里，他画了一个 $+$ 或 $-$（分别代表 $+1$ 和 $-1$）。

随着时间的推移，颜料褪色了，农夫约翰现在只记得某些格子的值。然而，农夫约翰确实记得关于原始涂色方案的一个重要事实：

在每一行和每一列中，任何连续子段的数值之和总是介于 $-1$ 和 $2$ 之间（含端点）。

作为一个例子，考虑行 $\texttt{+ - - +}$。它不满足条件，因为子段 $\texttt{+ [ - - ] +}$ 的和为 $-2$。

然而，行 $\texttt{- + + -}$ 确实满足条件：

[ - ] + + -    sum = -1
[ - + ] + -    sum = 0
[ - + + ] -    sum = +1
[ - + + - ]    sum = 0
- [ + ] + -    sum = +1
- [ + + ] -    sum = +2
- [ + + - ]    sum = +1
- + [ + ] -    sum = +1
- + [ + - ]    sum = 0
- + + [ - ]    sum = -1

请计算符合农夫约翰记忆的不同网格的数量。

输入格式

第一行包含 $T$（$1\le T\le 100$），即测试数据的组数。每组测试数据的格式如下：

第一行包含 $R$，$C$，和 $X$（$1\le R,C\le 5\cdot 10^5$，$0\le X\le \min(10^5,RC)$），意味着网格的尺寸为 $R\times C$，且农夫约翰记得网格中 $X$ 个不同格子的值。

接下来的 $X$ 行每行包含一个字符 $v\in \{+, -\}$，后跟两个整数 $r$ 和 $c$（$1\le r\le R, 1\le c\le C$），意味着网格第 $r$ 行第 $c$ 列的值是 $v$。保证在单组测试数据中，没有有序对 $(r,c)$ 出现超过一次。

此外，保证所有测试数据中 $R$ 的总和与 $C$ 的总和都不超过 $10^6$，且所有测试数据中 $X$ 的总和不超过 $2\cdot 10^5$。

输出格式

对于每组测试数据，在单独的一行中输出网格的数量。

样例 1

输入

2
1 3 3
+ 1 3
+ 1 1
- 1 2
1 3 3
+ 1 1
+ 1 3
+ 1 2

输出

1
0

样例 2

输入

1
2 2 0

输出

7

以下是这 $7$ 个网格：

++
++

++
+-

++
-+

+-
++

+-
-+

-+
++

-+
+-

数据范围与提示

• 测试点 3-4： 对于所有测试数据，$\min(R,C)=1$
• 测试点 5-6： 对于所有测试数据，$R,C\le 10$
• 测试点 7-11： $\sum \max(R,C)^2 \le 10^6$
• 测试点 12-14： $\sum RC \le 10^6$
• 测试点 15-22： 无额外约束

供题：Alex Chen