yukicoder No.1308 ジャンプビーコン

問題リンク

解説

公式解説のほうが賢いのでそちらを参考にしてください。

にいて にビーコンを置いてるときの最短距離

としましょう。

愚直にやると、ですが、ビーコンを置くのは通るpath上のどこかでいいのでHLDと双対セグ木を用いて、

でもとまります

提出コード

yukicoder.me