Simultaneous Coloring
Contest: Educational Codeforces Round 167 (Rated for Div. 2)
Difficulty rating: 3000
Tags: dfs and similar, divide and conquer, graphs

You are given a matrix, consisting of $$$n$$$ rows and $$$m$$$ columns.

You can perform two types of actions on it:

- paint the entire column in blue;
- paint the entire row in red.

Note that you cannot choose which color to paint the row or column.

In one second, you can perform either one action or multiple actions at the same time. If you perform one action, it will be free. If you perform $$$k > 1$$$ actions at the same time, it will cost $$$k^2$$$ coins. When multiple actions are performed at the same time, for each cell affected by actions of both types, the color can be chosen independently.

You are asked to process $$$q$$$ queries. Before each query, all cells become colorless. Initially, there are no restrictions on the color of any cells. In the $$$i$$$-th query, a restriction of the following form is added:

- $$$x_i~y_i~c_i$$$ — the cell in row $$$x_i$$$ in column $$$y_i$$$ should be painted in color $$$c_i$$$.

Thus, after $$$i$$$ queries, there are $$$i$$$ restrictions on the required colors of the matrix cells. After each query, output the minimum cost of painting the matrix according to the restrictions.

Input format:
The first line contains three integers $$$n, m$$$ and $$$q$$$ ($$$1 \le n, m, q \le 2 \cdot 10^5$$$) — the size of the matrix and the number of queries.

In the $$$i$$$-th of the next $$$q$$$ lines, two integers $$$x_i, y_i$$$ and a character $$$c_i$$$ ($$$1 \le x_i \le n$$$; $$$1 \le y_i \le m$$$; $$$c_i \in$$$ {'R', 'B'}, where 'R' means red, and 'B' means blue) — description of the $$$i$$$-th restriction. The cells in all queries are pairwise distinct.

Output format:
Print $$$q$$$ integers — after each query, output the minimum cost of painting the matrix according to the restrictions.

Constraints:
Time limit: 6.0 s
Memory limit: 512.0 MB

Example input:
2 2 4
1 1 R
2 2 R
1 2 B
2 1 B

Example output:
0
0
0
16

Example input:
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

Example output:
0
0
0
0
0
0
16
16
25
25

Editorial:
The main idea is as follows. Consider any constraint on a cell. If the cell must be red, then the last action on this cell must be coloring the row; otherwise, it should be the column. That is, if the operation is applied to both the row and the column of this cell, then there is a certain order of performing these operations. It is also worth noting that it does not make sense to apply the same operation twice, because the second application of the operation will recolor all the cells.
The word "order" should immediately bring to mind thoughts of directed graphs and topological sorting. Let's try to build a graph of operation execution. Create a graph with $$$n + m$$$ vertices — one vertex for each row and column. If the cell must be red, then draw a directed edge from its column to its row. Otherwise, draw an edge from its row to its column.
Now we would like to perform operations simply in the order of topological sorting. If this is possible (i.e., there are no cycles in the graph), then the answer is just $$$0$$$. This means that operations can always be applied one by one. It is also worth noting that we apply the operations that do not color any cells with constraints. Their cost is always $$$0$$$, so they do not change the answer.
Otherwise, there are some strongly connected components in the graph with size greater than $$$1$$$. In these components, we will always have to perform some operations at the same time. Of course, operations can be applied to the entire component at once. The cost will then be equal to the square of the component's size. Doesn't sound optimal but that's one way to satisfy the constraints.
Let's show that it is not possible to do it cheaper. Consider the last set of actions on this component. If they do not affect the entire component, then within the affected subset, there will be a vertex with an outgoing edge outside the subset, but inside the component (otherwise it would be two different components). This means that there must be at least one more operation performed on the vertex to which this edge leads. Therefore, the set of actions considered will not be the last one.
Then the solution is as follows. After adding each constraint, add the previously described edges and find the condensation of the graph. The answer will be the sum of the squares of the sizes of strongly connected components with size greater than $$$1$$$. This solution works in $$$O(q \cdot (n + m + q))$$$.
To optimize this solution, you can use the technique of incremental condensation. You can read about it in the blog by Radewoosh. Since DSU is used in it, you can maintain the sum of the squares of the component sizes on the fly.
The blog describes a solution with a logarithmic time complexity, but the problem did not require an implementation faster than $$$log^2$$$. Solutions with a logarithmic memory complexity with a large constant might not pass (the author's solution consumes $$$O(q \log q)$$$ memory and fits into $$$50$$$ megabytes).