◆ The contribution of each operation to the answer

By decomposing the answer into the contributions of the operations, we can see that computing the following for each \(i\) is the way to go:

• how many of the squares painted in the \(i\)-th query are not repainted until the end?

A square is not repainted if and only if neither the row nor column that contain the square becomes the target of an operation. Thus, if we can find the sets of rows and columns that appear in operations after the \(i\)-th one, we can easily see which squares are not repainted, enabling us to answer the question above.

◆ Solution

After all, the following information for each \(i\) enables us to find the answer.

• The set of rows that appear in operations after the \(i\)-th one
• The set of columns that appear in operations after the \(i\)-th one

Since the information of operations are accumulated backward, computing in the order \(i=Q, Q-1, \ldots, 2, 1\) enables us to perform the computation for all \(i\) efficiently.

Almost the same as above, but another understanding is that the final colors of the squares can be obtained as follows:

• For each \(i=Q,Q-1,\ldots,2,1\) in this order: paint the unpainted squares in the specified row or column.

.....   22222   22222   22222   22222   22222
.....   .....   ...2.   .4.2.   .4.2.   .4.2.
.....   .....   ...2.   .4.2.   34323   34323
.....   .....   ...2.   .4.2.   .4.2.   .4.2.

◆ Sample Implementation

https://atcoder.jp/contests/arc130/submissions/27292470