[過去ﾛｸﾞ] 競技プログラミングにハマるプログラマのスレ 143 (1002ﾚｽ)
上下前次1-新
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
252(2): 2023/12/22(金)03:55 AAS
>>250
そんな感じになるが、下限と上限の配列 ng(Q), ok(Q) を用意して log N 回行う：
1. 配列 t(Q) を, t[i] = (ng[i] + ok[i]) / 2 で定める
2. t(Q) と頂点を一緒にして重み降順ソートする
3. N 要素の UnionFind を用意する
4. 頂点重みの大きいほうから見ていく, t(Q) の要素にぶつかったら判定
5. i 番目の判定が true なら ok(i) ← t, そうでなければ ng(i) ← t
すみませんソートが入るから O((N+Q) log^2 (N+Q)) か
上下前次1-新書関写板覧索設栞歴
あと 750 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.009s