utils/scrapers/prescraped/codeforces/Editorials/1989F

Idea: BledDest
**Tutorial**
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).
**Solution (awoo)**