公式
B - Colorful Lines 解説 by maspy
◆ 各操作の答への影響
本問題の答を操作ごとに分解すると、各 \(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.
◆ 解答例
投稿日時:
最終更新: