以下の内容はhttps://jupiro.hatenablog.com/entry/2020/12/05/234702より取得しました。

解説

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

$dp[i][j] := x _ {i}$ にいて $j$ にビーコンを置いてるときの最短距離

としましょう。

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

$O(Q N (\log N) ^ 2)$ でもとまります

提出コード

以上の内容はhttps://jupiro.hatenablog.com/entry/2020/12/05/234702より取得しました。
このページはhttp://font.textar.tv/のウェブフォントを使用してます

不具合報告/要望等はこちらへお願いします。
モバイルやる夫Viewer Ver0.14