[過去ﾛｸﾞ] 競技プログラミングにハマるプログラマのスレ 143 (1002ﾚｽ)
上下前次1-新
抽出解除 ﾚｽ栞
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
238(2): 2023/12/22(金)02:01 AAS
一応ちゃんと想定を書く
各クエリをLCAで2つのパスに分解して、子孫のほうに情報を持たせておく。
そしてminセグ木を一つ持って、dfs順に頂点iを走査しセグ木の要素をA_iに更新する（このときのセグ木のインデックスは頂点iの根からの距離）。すると、iの祖先が根から順番にセグ木に並んでいる状態になるので、iに持たせたパスクエリについてRMQで答えが求まる。
最後に各クエリについて、分解した2つのパスの答えから小さい方を取って答える。
だいぶ日本語がアレになったけど許して
241(1): 2023/12/22(金)02:18 AAS
>>238
似たようなこと考えてたけど、セグ木じゃなくてmultisetでシミュするだけで良さそうだと思った
242: 2023/12/22(金)02:19 AAS
>>238,241
ごめん、LCAの上の爺も残るので嘘でした
上下前次1-新書関写板覧索設栞歴
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.762s*