ABC477 D - Masking Tape
マスキング
考え方
愚直にやると、$O(NQ)$ で明らかにTLE。
よって、高速化が必要。
そして「それまでの状況を見ることもなく破棄してこうする」系問題には、バックトレースが有効。
すなわち、逆再生の中で最初に塗られたときを考えればいい。
とはいえ、最後にタイルがあるかないかは普通にシミュレーションしないとわからない。
よって、順方向 $\to$ 逆方向と $2$ 回シミュレーションする。
最初にクエリ $1$ のみシミュレーションをし、最後のタイルの様子を求める。
そこから $1$ つずつ巻き戻していく。
クエリ $1$ は、普通にタイルの反転処理をする。
クエリ $2$ は、一度も塗ったことがなくタイルがないところを全て塗る。
これを実装するには、以下の $2$ つのデータを set か何かで持つとよい。
- 一度も塗ったことがなく、タイルがあるマス一覧
- 一度も塗ったことがなく、タイルがないマス一覧
バックトレース終了まで一度も塗られなかったマスは、'a' を書き込む。
計算量は $O((N+Q)\log N)$ である。
入力例1での動作
入力を受け取る。
n: 3
q: 5
queries:
1 2
2 b
1 1
1 2
2 c最初にクエリ $1$ だけを順方向に処理して、最後のタイルの状態を求める。
| 処理 | タイルがあるマス |
|---|---|
| 開始時 | なし |
1 2 |
$2$ |
1 1 |
$1,2$ |
1 2 |
$1$ |
したがって、全クエリ終了時にはマス $1$ にだけタイルがある。
ここからクエリを逆順に処理する。
色がまだ確定していないマスだけについて、タイルがあるかないかを管理する。
開始時は、タイルがある未確定マスが $\{1\}$、タイルがない未確定マスが $\{2,3\}$ である。
| 逆向きに見るクエリ | タイルありの未確定マス | タイルなしの未確定マス | 確定した色 |
|---|---|---|---|
| 開始時 | $\{1\}$ | $\{2,3\}$ | なし |
2 c |
$\{1\}$ | $\{\}$ | $2,3$ が c |
1 2 |
$\{1\}$ | $\{\}$ | $2,3$ が c |
1 1 |
$\{\}$ | $\{1\}$ | $2,3$ が c |
2 b |
$\{\}$ | $\{\}$ | $1$ が b、$2,3$ が c |
最後に、バックトレース終了まで一度も塗られなかったマスがないか確認する。
この入力では、該当するマスはない。
全てのマスの色が確定し、最終的な文字列は bcc となる。
注意点
特になし。
別解
特になし。