まず、\(X\) を求めるステップについて観察します。
2における \(m\) は \([l,r]\) を \(b_j : a_j\) に内分する点の小数点以下を切り捨てた値です。もし \(m\) が \(i\) に一致すればそれまでの繰り返しの回数を \(x_i\) とし、そうでなければ \([l,r]\) のうち \(m\) より小さい部分と大きい部分のうち、\(i\) が属する方に \([l,r]\) を置き換えます。ここで、\(\max (\frac{a_i}{b_i}, \frac{b_i}{a_i})\leq 2\) より置き換え後の区間の長さは元の区間の \(\lceil \frac{2}{3}\rceil\) 以下になるといえ、\(i\) を求めるための繰り返しの回数は \(\mathrm{O}(\log N)\) 回と分かります。

\(X\) を求めるステップ中に現れる \([l,r]\) に対応する二分木を以下のように定めます。

• 根の番号が \([l,r]\) に対する \(m\) で、左の子を根とする部分木は \([l,m-1]\) に対応する二分木、右の子を根とする部分木は \([m+1,r]\) に対応する二分木(区間が空の場合は子を持たない)

これは二分木に対する通りがけ順による番号づけです。また、\(x_i\) は \([1,N]\) に対応する二分木の頂点 \(i\) の深さです。このことから \(x_i-x_{i+1}\) は頂点 \(i\) と頂点 \(i+1\) の深さの差の絶対値と言えますが、通りがけ順の番号づけにおいて番号が隣接する頂点は祖先・子孫の関係になっているため、単に頂点 \(i\) と頂点 \(i+1\) の距離となります。よって、求めるべき値は頂点 \(c_i,c_i+1,\ldots,d_i\) をこの順番で通る経路の長さです。
\(c_i\) 以上 \(d_i\) 以下の頂点に対する最小シュタイナー木を \(T\) とします。また、深さ最小の点を \(r\) とします(元の木における \(c_i\) と \(d_i\) の最近共通祖先です)。「\(r\) から始めて \(c_i,c_i+1,\ldots,d_i\) と訪問し、\(r\) に戻る」というのは \(T\) の対するDFSに等しく、経路長は \(2 \times \)(辺数 \(=\) 頂点数 \(-1\) ) となります。また、元の問題の答えはこの値から \(c_i\) と \(d_i\) の距離を引けば求められます。よって、\(T\) の頂点数と \(c_i\) と \(d_i\) の距離が分かれば本問に答えられます。特に、\(T\) の頂点は「番号が \(c_i\) 以上 \(d_i\) 以下の頂点」と「\(c_i, d_i\) 間のパス上にある番号が \(c_i\) 未満または \(d_i\) より大きい頂点」の和集合であることを考えると頂点数を簡単に求められるでしょう。
具体的な処理を述べます。まず、\(c_i\) と \(d_i\) の最小共通祖先 \(r\) までDFSでもぐります(\(c_i,d_i\) がともに \(m\) 未満または \(m\) より大きい場合に、前者ならば左の子へ、後者ならば右の子へ行きます)。その後、\(r\) から \(c_i, d_i\) までの経路を独立にたどります。\(T\) の頂点数は先述の通り \(c_i,d_i\) パス上の頂点番号を見ればよく、距離は \(x_{c_i} + x_{d_i} - 2x_{r}\) として求められます。最初に述べたように繰り返しは \(\mathrm{O}(\log N)\) 回となるため、二分木の深さについても同じことが言え、このアルゴリズムのステップ数も \(\mathrm{O}( \log N)\) といえます。