[過去ﾛｸﾞ] 競技プログラミングにハマるプログラマのスレ 143 (1002ﾚｽ)

競技プログラミングにハマるプログラマのスレ 143 http://medaka.5ch.net/test/read.cgi/prog/1703141733/

上下前次1-新
通常表示 512ﾊﾞｲﾄ分割 ﾚｽ栞
抽出解除 ﾚｽ栞

---

このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ

---

ﾘﾛｰﾄﾞ規制です｡10分ほどで解除するので､他のﾌﾞﾗｳｻﾞへ避難してください｡

---

238: 仕様書無しさん [sage] 2023/12/22(金) 02:01:41.74 一応ちゃんと想定を書く 各クエリをLCAで2つのパスに分解して、子孫のほうに情報を持たせておく。 そしてminセグ木を一つ持って、dfs順に頂点iを走査しセグ木の要素をA_iに更新する（このときのセグ木のインデックスは頂点iの根からの距離）。すると、iの祖先が根から順番にセグ木に並んでいる状態になるので、iに持たせたパスクエリについてRMQで答えが求まる。 最後に各クエリについて、分解した2つのパスの答えから小さい方を取って答える。 だいぶ日本語がアレになったけど許して http://medaka.5ch.net/test/read.cgi/prog/1703141733/238

241: 仕様書無しさん [sage] 2023/12/22(金) 02:18:56.00 >>238 似たようなこと考えてたけど、セグ木じゃなくてmultisetでシミュするだけで良さそうだと思った http://medaka.5ch.net/test/read.cgi/prog/1703141733/241

242: 仕様書無しさん [sage] 2023/12/22(金) 02:19:41.20 >>238,241 ごめん、LCAの上の爺も残るので嘘でした http://medaka.5ch.net/test/read.cgi/prog/1703141733/242

---

ﾒﾓ帳

(0/65535文字)

---

上下前次1-新書関写板覧索設栞歴

---

ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ

---

Google検索

Wikipedia

---

ぬこの手 ぬこTOP 0.032s