そうそう、ドワンゴの問題とこれでブルーフカ法を知ったんだよね。
https://atcoder.jp/contests/keyence2019/tasks/keyence2019_e
問題
N個の頂点がある。
ここに(N-1)本の辺を張り木を構成したい。
各点iにはパラメータA[i]が設定されている。
頂点i-j間に辺を張るときのコストは定数Dを用いて|i-j|*D+A[i]+A[j]とするとき、最小全域木のコストを求めよ。
解法
複数の解法がある。
1つ目はブルーフカ法。
まずここで重要な知見として、辺は互いに交差しない。
つまりLa-Ra間とLb-Rb間を結ぶ辺があるとき、La<Lb<Ra<Rbのようにはならない。
これは、ブルーフカ法で徐々に連結成分を求めていくとき、連結成分は常にある連続区間になることを示す。
ということは、次のステップでは各頂点から連結成分の外側、つまり最大2つの連続区間におけるコストの最小値を求めればよく、これはSegTreeで容易に計算できる。
もう一つは辺の張り替え。
まず頂点(0,N-1)間で辺を張っているとする。
以後、1~(N-2)の各点について、左右いずれかコストの最も低い点に辺を張る、ということを行う。
これで全体が連結になる。
例えば頂点3-4間が極端にコストが低く、互いに辺を張ろうとした場合、元々(0,N-1)間に辺があるので、(0,N-1)と(3,4)間に辺があるのは、(0,3)(3,4)(4,N-1)間に辺があるのとコストは同じで、かつ登場する頂点間を連結にできる。
同じ要領で全頂点これだけで連結にできる。
こちらはSegTreeすら要らない。
int N; ll D; ll A[202020]; ll L[202020],R[202020]; void solve() { int i,j,k,l,r,x,y; string s; cin>>N>>D; ll ret=0; FOR(i,N) { cin>>A[i]; ret+=A[i]; L[i]=max((i?L[i-1]:-1LL<<60),i*D-A[i]); } ret+=(N-1)*D; for(i=N-1;i>=0;i--) { R[i]=min((i<N-1?R[i+1]:1LL<<60),i*D+A[i]); if(i>0 && i<N-1) ret+=min(i*D-L[i],R[i]-(i*D)); } cout<<ret<<endl; }
まとめ
後者の解法もちらっと思い浮かんだのだけどなぁ。