競技プログラミング用 知識集積所
ABC455D - Card Pile Query
最終更新：
sport_programming
-
view
問題
必要知識
B以下レベルの内容は省略
- 逆写像※っぽいもの（全射でないので厳密にはそうではないのだが）
考え方
複雑なことをしているようで、実はそうでもない。
クエリで「X Y」が来た場合、XがYの上に乗る。
その後クエリがたくさん来たとして、「X 何か」というクエリが来ない限り、XがYの上にあるという関係は実は壊れることがない。
ということで、「最終的に何の下に何があるか」はクエリを見て単純に情報を書き換えていくだけでよい。
このとき、-1などで初期化することで、下には何もない（最初から一度も動いていない）情報も残すことができる。
クエリで「X Y」が来た場合、XがYの上に乗る。
その後クエリがたくさん来たとして、「X 何か」というクエリが来ない限り、XがYの上にあるという関係は実は壊れることがない。
ということで、「最終的に何の下に何があるか」はクエリを見て単純に情報を書き換えていくだけでよい。
このとき、-1などで初期化することで、下には何もない（最初から一度も動いていない）情報も残すことができる。
解答には「最終的に何の下に何があるか」が欲しいのだが、これも実は簡単である。
「最終的に1の下に4がある」なら、「最終的に4の上に1がある」わけで、逆写像※に近い考え方を用いて構成できる。
「最終的に1の下に4がある」なら、「最終的に4の上に1がある」わけで、逆写像※に近い考え方を用いて構成できる。
それらを全て作ったら、各i番について、
- i番の下に何かあるなら、i番の山は空っぽになっているので答えは0
- i番の下に何もないなら、i番のカードの上、その上、さらに上、と上のカードがなくなるまで辿って枚数を数える
を実行することで答えが出る。
この部分の計算量は、各カード最大2度しか見ないので、O(N)である。
この部分の計算量は、各カード最大2度しか見ないので、O(N)である。
