名前のよくわからないデータ構造について紹介します。 そのデータ構造は、ある順列を受け取り、 深さ0ではその順列をそのまま配列にして、深さ1では中央mdで深さ0のときの配列を分け、ｍｄより小さいものはmdより小さいindex、mdより大きいものはmdより大き…

なんかPKUのコードあさると時々見るSPFAというアルゴリズムを紹介します。 SPFAは単一始点の最短経路アルゴリズムで、負辺があっても動作します。 shortest path faster algorithmとかいうたいそうな名前がついてますが、普通はダイクストラに比べ遅いです。…

みんな大好き永続赤黒木！！！！！！ 書いてみると、むちゃくちゃなほど実装重いというわけではないです。重いですが。 正直言って書くより何故赤黒木がうまくいくのかを理解したほうがいいとおもう(今更)赤黒木の実装の本質は、hosさんのスライドの解説とほ…