segtreeがやたら書きたくなったのでPKU漁ったら出てきた問題。 解法 区間の最大値と最小値の差を出力する問題。普通に2つのsegtreeで区間の最大値、最小値を求めて引き算しました。 ソースコード #include <cstdio> #include <cstring> #include <cstdlib> #include <cmath> #include <complex> #includ</complex></cmath></cstdlib></cstring></cstdio>…

解法 まず全店舗からダイクストラして、最寄りの店までの最短距離(dist[i])を求める。 L[i][j](iとjを結ぶ道の距離)>abs(dist[i]-dist[j])ならばその道上の最も遠くなる場所までの距離は max(dist[i],dist[j])+(L[i][j]-abs(dist[i]-dist[j]))であるから、そ…