公式解説と同様の方針で、根付き木 \(G\) を構築しない解法を紹介します。 \(n(x) (1 \le x \le 2N)\) を、「区間 \(1, 2, \cdots, M\) のうち \(x\) を含む区間の個数」とすると、\(n(x)\) は根付き木 \(G\) における頂点 \(m(x)\) の深さに対応しています(下図参照)。

すると、各クエリの答えである「根付き木 \(G\) での頂点 \(m(C_j), m(D_j)\) 間の最短経路の長さ」は、\(n(C_j)+n(D_j)-2n(a)\) （ \(a\) は \(m(C_j), m(D_j)\) のLCA）で求めることができます。そして、\(n(a)\) は \(n(x)\) の区間 \([C_j,D_j]\) 内の最小値として求めることができます。 よって、区間加算・区間最小値取得ができる遅延セグメント木を用いれば、

• \(n(x)\) の作成：遅延セグメント木への区間加算
• \(n(a)\) の取得：遅延セグメント木の区間最小値取得

で済み、少ない実装量でACすることができます。 計算量は \(O((M+Q) \log N)\) です。