第二回全国統一プログラミング王決定戦予選-D Shortest Path on a Line

概要

最大10^5個の頂点(それぞれ1~Nまで番号を振る)を持つ辺に次の最大10万個のqueryで無向辺を追加する。

クエリ
LとRとCを与えられる。 $L <= a < b <= R$ を満たすすべての(a, b)の間にコストCの辺を張る。

クエリを全部処理したのち、頂点1から頂点Nまでの最短経路問題を解け。

ACするまで

1. みんな通してるなぁー。~~制約的にDAGっぽい？~~－＞嘘でした
2. 愚直に辺を張ると辺の数が $O(N^3)$ になる。すぬけ君の地下鉄旅行のターミナル駅を作る手法をしてもなお $O(N^2)$ となり険しい。
3. データ構造でうまくやれないかなーと考える。->非想定解法でデータ構造で殴れます。(後程この記事に加筆)

4. 解説を参照。 $[L, R$ ]間ですべてに辺を張ることを、天才的な言い換えをすることで辺の数を $O(N)$ にすることができる。2で述べた手法とは違い、これはほかのqueryでも再利用できる辺の貼り方をしてる。
5. AC

考察

この問題のキモはいかにして条件を保ったまま辺の数を減らすかである。もともとは $O(N^3)$ であるが、どうにかして最終的には $O(N)$ にしないといけない。

ターミナル駅を作る手法の詳細はこちらの記事を見てください。

ターミナル駅をつくる手法は $O(N^2)$ に辺の数を落とせるが、それ以上の抜本的な改善は難しい（はず）

解説解法

ここで、解説の紹介してた辺の貼り方を説明する。

補題　 $d_1 <= d_2 <= ... <= d_n$ が成り立つ。

ひとまず、頂点1から離れれば離れるほど距離が遠くなることを証明する。(感覚ではそうなるけど)

$d_i > d_{i+1}$ が成り立つと仮定する。
適切な頂点 t から距離cの辺をたどって、頂点 i+1 に行きつくのが最短距離であるので、 $d_{i+1}=d_t+c$ と、辺のコストcを使って書ける。
ここで、 $i > t$ であるとき、同様に $d_i = d_t+c$ と書けるが、これは仮定と矛盾する。
$i = t$ の時、 $d_{i+1}=d_i+c$ と式はなるが、これも家庭と矛盾する。
よって、これをすべての $i$ に適用させれば、距離は頂点1から離れるごとに広義単調増加することを示せた。