[過去ﾛｸﾞ] 競技プログラミングにハマるプログラマのスレ 227 (1002ﾚｽ)
上下前次1-新
このｽﾚｯﾄﾞは過去ﾛｸﾞ倉庫に格納されています｡
次ｽﾚ検索 歴削→次ｽﾚ 栞削→次ｽﾚ 過去ﾛｸﾞﾒﾆｭｰ
260: 05/22(木)02:21 AAS
次に、ポテンシャルの変化 ΔΦ を評価します。パス上の各ノード x_i に注目します。
- ケース1: x_i が元々RightHeavyだった場合
size(R_i) > size(L_i) であったため、Φ に +1 貢献していました。
スワップ後、x_i の新しい右の子は L_i、新しい左の子は R'_i となります。
size(L_i) < size(R_i) であり、size(R'_i) は size(R_i) と同程度かそれ以上になる傾向があるため、size(L_i) <= size(R'_i) となる可能性が高いです。この場合、x_i はRightHeavyではなくなります。
したがって、x_i によるポテンシャルの変化は -1 となります。
- ケース2: x_i が元々RightHeavyではなかった場合
省9
上下前次1-新書関写板覧索設栞歴
あと 742 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.010s