区間に辺を貼る一般的なテクニック

区間に辺を貼る一般的なテクニック from CuriousFairy315

実際にこの手法が使える練習問題
D - Shortest Path on a Line

参考記事

実際にセグ木式の実装例が乗っています