最短経路への帰着

次の最短経路問題に帰着できます。

• 頂点は \(0, 1, \cdots, N\) の \(N+1\) 個である。
• \(1 \le i \le K-1\) に対し、 \((i+1)\) から \(i\) にコスト \(0\) の辺が張られている
• \(1 \le i \le N\) に対し、 \((L_i-1)\) から \(R_i\) にコスト \(1\) の辺が張られている
• 頂点 \(0\) から \(N\) までの最短距離がこの問題の答えである。

ただし、本問題では \(N\) が \(10^9\) と巨大になってしまい、実行時間制限やメモリ制限に引っかかる可能性があります。

座標圧縮

そこで、登場する座標 \(\bigcup_i \{L_i-1, R_i\} \cup \{0, N\}\) を圧縮し、小さい方から \(\{0, 1, \cdots, k\}\) に直します。（座標圧縮 と言われるテクニックです）。そうすると、先ほどの頂点数 \(N+1\) の最短経路問題は頂点数が高々 \(2M+2\) 、辺数が高々 \(3M+1\) の最短経路問題に自然に帰着できます。

この最短経路問題は Dijkstra 法を使っても \(O(M \log M)\) 時間で解けますが、辺のコストが \(0\) または \(1\) のいずれかであるため、01 BFS と呼ばれるテクニックを使えば \(O(M)\) 時間でさらに高速に解くことができます。

ただし、座標圧縮に \(O(M \log M)\) 時間かかっているため、01 BFS を使ってもこの問題を解くための全体の計算量としては \(O(M \log M)\) になります。

時間計算量は \(O(M \log M)\) 、空間計算量は \(O(M)\) です。

実装例

C++, 117 ms https://atcoder.jp/contests/awc0006/submissions/73370210