← 返回题目列表

Codeforces · 1989/F

F. 同步着色

中文机器翻译题面 查看原题

给定一个矩阵,由 $$$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$$$ {'R', 'B'},其中 'R' 表示红色,'B' 表示蓝色)—第 $$$i$$$ 限制的描述。所有查询中的单元格都是成对不同的。

输出

打印 $$$q$$$ 整数 - 在每次查询后,输出根据限制绘制矩阵的最小成本。

示例

输入 #1

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

输出 #1

0
0
0
16

输入 #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