頂点 \(s\) から頂点 \(t\) への最短パス（重みが最小のパス）を考えます。 以下、頂点 \(v\) に対して \(A_v \coloneqq [L_v, R_v]\) とします。

まず、\(A_s\) と \(A_t\) が互いに素かどうかは \(O(1)\) 時間で判定でき、もしそうであれば \(s\) と \(t\) は \(G\) 上で隣接しているため、答えは \(W_s + W_t\) とわかります。 以下、\(A_s\) と \(A_t\) が交わる場合を考えます。

このとき、最短パス \(P\) は \(s, t\) とは異なる頂点を経由します。 特に、\(s\) に隣接する経由点 \(u\) と、\(t\) に隣接する経由点 \(v\) がそれぞれ唯一存在します。

• \(u = v\) のとき、\(P\) は \(s \to v \to t\) というパスです。

• \(u \neq v\) のとき、\(u\) と \(v\) は隣接していることが次の「詳細」に述べる通りにわかるため、\(P\) は \(s \to u \to v \to t\) というパスです。

  一般性を失わず \(L_s \leq L_t\) と仮定できます。
  もし \(A_s\supseteq A_t\) とすると \(s\) の隣接点は \(t\) の隣接点でもあることになり \(u \neq v\) に矛盾するため、\(R_s \lt R_t\) でなければなりません。このことと \(A_s\) と \(A_t\) は交わりを持つことを合わせると \(L_t \leq R_s\) がわかります。
  \(u\) は \(s\) に隣接するが \(t\) に隣接しないので \(L_u \gt R_s\) が成り立ち、\(v\) に関しても同様に \(R_v \lt L_t\) が成り立ちます。
  以上から、\(R_v \lt L_t \leq R_s \lt L_u\) が得られ、\(A_u\) と \(A_v\) は互いに素であることがわかります。

よって、最短パスを求める際には、その候補として下記の \(2\) つの形のパスのみを考慮すれば十分です。

• \(s, t\) の両方に隣接するある頂点 \(v\) を通る、\(s \to v \to t\) というパス。
• \(s\) に隣接するが \(t\) には隣接しないある頂点 \(u\) と、 \(t\) に隣接するが \(s\) には隣接しないある頂点 \(v\) を通る、\(s \to u \to v \to t\) というパス。

上記の \(2\) ケースそれぞれで重み最小のパスを求めることは、 あらかじめ、各 \(i = 0, 1 ,2, \ldots, 2N+1\) に対する

\[a[i] \coloneqq \min_{R_v \leq i} W_v, \quad b[i] \coloneqq \min_{L_v \geq i} W_v\]

を前計算しておくことで効率的に計算できます。 例えば、\(s \to v \to t\) の形のパスの重みの最小値は、 \(L \coloneqq \min\lbrace L_s, L_t\rbrace, R \coloneqq \max\lbrace R_s, R_t\rbrace\) によって \(\min\lbrace a[L-1], b[R+1]\rbrace\) と表されて \(O(1)\) 時間で求められることが、

\[ \begin{aligned} v \text{が} s, t \text{の両方に隣接する} &\iff A_v \cap (A_s \cup A_t) = \emptyset \\ &\iff A_v \cap ([L, R]) = \emptyset\\ &\iff R_v \lt L \text{または} L_v \gt R \end{aligned} \]

からわかります。

\(a[\,], b[\,]\) の前計算は \(O(N)\) 時間で可能であり、これを用いてクエリを \(1\) 個あたり \(O(1)\) 時間で処理できるため、 本問題を \(O(N+Q)\) 時間で解くことができます。