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$ 个整数，每次询问后输出满足所有限制的最小涂色花费。

由 ChatGPT 4.1 翻译