CF1989F Simultaneous Coloring

题目描述

给定一个由 $n$ 行 $m$ 列组成的矩阵。

你可以对其执行两种操作：

• 将整列涂成蓝色；
• 将整行涂成红色。

注意，你不能选择行或列要涂成哪种颜色。

在一秒内，你可以执行一次操作，也可以同时执行多次操作。如果只执行一次操作，则不需要花费。如果同时执行 $k>1$ 次操作，则需要花费 $k^2$ 个硬币。当多次操作同时进行时，对于同时受到两种操作影响的每个格子，其颜色可以独立选择。

你需要处理 $q$ 个询问。在每次询问前，所有格子都会变为无色。最初，对任何格子的颜色都没有限制。在第 $i$ 次询问中，会增加如下形式的限制：

• $x_i~y_i~c_i$ ——第 $x_i$ 行第 $y_i$ 列的格子必须被涂成颜色 $c_i$。

因此，在第 $i$ 次询问后，共有 $i$ 个格子的颜色有要求。每次询问后，输出按照所有限制涂色所需的最小花费。

输入格式

第一行包含三个整数 $n, m, q$（$1 \le n, m, q \le 2 \cdot 10^5$），分别表示矩阵的行数、列数和询问数。

接下来的 $q$ 行中，第 $i$ 行包含两个整数 $x_i, y_i$ 和一个字符 $c_i$（$1 \le x_i \le n$；$1 \le y_i \le m$；$c_i \in \{\text{R}, \text{B}\}$，其中 'R' 表示红色，'B' 表示蓝色），表示第 $i$ 次限制。所有询问中的格子两两不同。

输出格式

输出 $q$ 个整数，每次询问后输出满足所有限制的最小涂色花费。

输入输出样例 #1

输入 #1

2 2 4
1 1 R
2 2 R
1 2 B
2 1 B

输出 #1

0
0
0
16

输入输出样例 #2

输入 #2

3 5 10
1 1 B
2 5 B
2 2 B
2 3 R
2 1 B
3 2 R
3 3 B
1 2 R
1 3 B
3 1 B

输出 #2

0
0
0
0
0
0
16
16
25
25

说明/提示

由 ChatGPT 4.1 翻译