LR Minimum Spanning Tree

解説

$p_i, q_i$ をそれぞれ $(L_1, L_2, \dots, L_i), (R_i, R_{i+1}, \dots, R_N)$ の最小値をとる添字のうち最小のものとする。

$1 \le i \lt N$ に対して、次の $3$ つの辺を考える。

• 頂点 $p_i$ と頂点 $i+1$ を結ぶ辺
• 頂点 $i$ と頂点 $q_{i+1}$ を結ぶ辺
• 頂点 $p_i$ と頂点 $q_{i+1}$ を結ぶ辺

これら $3(N-1)$ 本の辺を 良い辺 とする。 良い辺 のみを用いて最小全域木が必ず存在することを示す。

頂点 $i$ と頂点 $j$ を結ぶ辺を考える。ただし $(i \lt j)$ とする。

$i \le k \lt j$ を満たす任意の $t$ について

$$L_{p_k} \le L_i, ~ R_{q_{k+1}} \le R_j$$

であるので頂点 $p_k$ と頂点 $q_{k+1}$ を結ぶ辺の重みは $L_i + R_j$ 以下である。

また、$p_k \neq p_{k+1}$ かつ $q_k \neq q_{k+1}$ のとき、$p_{k+1} = q_{k+1} = k+1$ であるので、頂点 $p_k$ と頂点 $q_{k+1}$ を結ぶ辺と、頂点 $p_{k+1}$ と頂点 $q_{k+2}$ を結ぶ辺は必ず端点を共有する。

すなわち、頂点 $i, j$ $(i \lt j)$ において、重み $L_i + R_j$ 以下の 良い辺 のみからなる長さ $2$ 以上のパスが存在する。

良い辺 以外の辺 $(x, y)$ を含む最小全域木 $T$ があると仮定する。 $T$ から辺 $(x, y)$ を削除するとグラフ $2$ つの連結成分 $S_1, S_2$ に分かれる。 重み $L_i + R_j$ 以下の 良い辺 であって $S_1, S_2$ を連結にするようなものは必ず存在するので、これを追加することで再び最小全域木を構成できる。この操作を繰り返すことで、 良い辺 のみからなる最小全域木が必ず存在することが示された。

よって、$3(N-1) = O(N)$ 本の辺を用いてクラスカル法などで最小全域木を求めることで、 $O(N \log{N})$ でこの問題を解くことができた。