A - Complement Interval Graph Editorial by evima
Consider the shortest path (the path of minimum weight) from vertex \(s\) to vertex \(t\). Let \(A_v \coloneqq [L_v, R_v]\) for each vertex \(v\).
First, whether \(A_s\) and \(A_t\) are disjoint can be determined in \(O(1)\) time. If they are disjoint, \(s\) and \(t\) are adjacent in \(G\), so the answer is \(W_s + W_t\). Below, assume \(A_s\) and \(A_t\) intersect.
In that case, the shortest path \(P\) will pass through vertices other than \(s\) and \(t\). In particular, there are exactly one via point \(u\) that is adjacent to \(s\) and one via point \(v\) that is adjacent to \(t\):
- If \(u = v\), then the path \(P\) is \(s \to v \to t\).
- If \(u \neq v\), it can be shown (see “Details” below) that \(u\) and \(v\) are adjacent, so \(P\) is \(s \to u \to v \to t\).
Details
Without loss of generality, assume \(L_s \leq L_t\).
If \(A_s \supseteq A_t\), then the vertex adjacent to \(s\) would also be adjacent to \(t\), contradicting \(u \neq v\). Thus \(R_s < R_t\) must hold. This, combined with the fact that \(A_s\) and \(A_t\) intersect, tells us \(L_t \leq R_s\).
Since \(u\) is adjacent to \(s\) but not adjacent to \(t\), it follows \(L_u > R_s\). Similarly, \(R_v < L_t\).
Hence, \(R_v < L_t \leq R_s < L_u\). This shows \(A_u\) and \(A_v\) are disjoint.
Therefore, to find the shortest path, it suffices to consider only the following two forms of paths:
- A path of the form \(s \to v \to t\), where \(v\) is adjacent to both \(s\) and \(t\).
- A path of the form \(s \to u \to v \to t\), where \(u\) is adjacent to \(s\) but not \(t\), and \(v\) is adjacent to \(t\) but not \(s\).
We can efficiently compute the minimum-weight path for the above two cases by precomputing the following for each \(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\]
For example, to find the minimum weight of a path of the form \(s \to v \to t\), let \(L \coloneqq \min\lbrace L_s, L_t\rbrace, R \coloneqq \max\lbrace R_s, R_t\rbrace\). Then, the minimum weight of such a path can be expressed as \(\min\lbrace a[L-1], b[R+1]\rbrace\), which can be found in \(O(1)\) time. This follows from:
\[ \begin{aligned} v \,\, \text{is adjacent to both} \,\, s \,\, \text{and} \,\, t &\iff A_v \cap (A_s \cup A_t) = \emptyset \\ &\iff A_v \cap ([L, R]) = \emptyset\\ &\iff R_v \lt L \,\, \text{or} \,\, L_v \gt R \end{aligned} \]
We can compute \(a[\,]\) and \(b[\,]\) in \(O(N)\) time. Then, each query can be answered in \(O(1)\) time. Thus, the problem can be solved in \(O(N + Q)\) time overall.
posted:
last update: