◆ 各操作の答への影響

本問題の答を操作ごとに分解すると、各 \(i\) に対して次が計算できればよいことが分かります：

\(i\) 番目のクエリで塗った色のうち、最後まで上書きされないものはいくつあるか？

あるマスが一度も上書きされないことと、それを含む行・列がともに操作対象とならないことは同値です。したがって、\(i\) 番目より後の操作に現れる行の集合・列の集合を求めることができれば、上書きされないマスがどのようなものであるかは簡単に分かり、上述の問に答えることができます。

◆ 計算方法

結局各 \(i\) に対して、次の情報があれば答を求めることができます。

• \(i\) 番目よりも後の操作で操作対象となる行の集合
• \(i\) 番目よりも後の操作で操作対象となる列の集合

後の操作の情報を累積していくため、\(i=Q, Q-1, \ldots, 2, 1\) の順に計算していくことで、すべての \(i\) に対する計算を効率よく行うことができます。

ほとんど同じことですが、最終的なマス目の色は、次の操作により得られると理解することもできます：

• \(i=Q,Q-1,\ldots,2,1\) 順に次を行う：指定された行や列のうち未着色の部分に指定された色を塗る

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

◆ 解答例

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