この問題ではグラフの辺の数が最大で \(NQ\) 本となるため、一般の最小全域木を求めるアルゴリズムをそのまま適用することができません。

グラフの形状が特殊であることを利用して、Kruskal 法をベースに高速化を行うことを考えます。

まず辺のコストでソートを行い、適切に頂点の番号を付け替えることで \(C_1 \leq C_2 \leq \ldots \leq C_Q\) の場合に帰着します（実装上では頂点の番号の付け替えは不要になることが多いかもしれません）。

Kruskal 法のアルゴリズムを考えると、最小全域木は以下のような手順で求められることがわかります。

• \(N + Q\) 頂点の辺がないグラフを用意する。
• \(i = 1, 2, \ldots ,Q\) の順に以下のような操作を行う。
  • \(j = L_i, L_i + 1, \ldots, R_i\) の順に頂点 \(N + i\) と頂点 \(j\) が連結でないとき、またそのときに限り頂点 \(N + i\) と頂点 \(j\) の間にコスト \(C_i\) の辺を追加する。

このままではまだ条件を扱いにくいですが、\(j =L_i\) のときは必ず頂点 \(N + i\) と頂点 \(j\) は連結でなく、\(j > L_i\) のときは頂点 \(N + i\) と頂点 \(j - 1\) は連結であるため頂点 \(N + i\) と頂点 \(j\) の連結性は頂点 \(j - 1\) と頂点 \(j\) の連結性と同値であることから、連結判定は番号が隣り合った頂点 \(j -1, j\) にのみ行うことができればよいことがわかります。また、グラフが非連結であることと頂点 \(j - 1\) と頂点 \(j\) が非連結であるような \(1\) 以上 \(N\) 未満の整数 \(j\) が存在することが同値です。

これを愚直に実装すると時間計算量は \(\Theta(NQ + Q\log Q)\) のままですが、上記のような単純な設定に帰着したことで様々な高速化の方法があります。

以下高速化の方法の例を 3 つ紹介します。

(1) set (やそれに類するデータ構造)を用いる

C++ における std::set やそれに類するデータ構造で \(1 \leq j < N\) であって頂点 \(j\) と \(j + 1\) が連結でないものの集合を保持しておき、\(L_i, L_i + 1, \ldots, R_i - 1\) のうち set に入っているものを順に削除すればよいです。各要素が set に入っているかを愚直に判定するとやはり TLE となりますが、std::set における lower_bound のような \(x\) 以上の最小の要素を高速に取得できる関数を用いれば全体として要素の削除は高々 \(N - 1\) 回しか起きないことから時間計算量は \(O((N + Q) \log N)\) で評価でき、十分高速です。

(2) lazy segment tree を用いる

区間和取得 / 区間を \(0\) で更新する lazy segment tree を用いるという方法もあります。lazy segment tree の \(j\) 番目の要素を頂点 \(j\) と頂点 \(j + 1\) が連結のとき \(0\)、そうでないとき \(1\) となるようにします。長さ \(N - 1\) の lazy segment tree を各要素 \(1\) で初期化し、\([L_i, R_i)\) の区間和を取得することが頂点 \(N + i\) と頂点 \(L_i + 1, L_i + 2, \ldots, R_i\) を結ぶ辺の数に対応します。そして、辺を張ることが \([L_i, R_i)\) を \(0\) に更新することに対応します。

(3) bit 演算を用いる

配列を用いて順に確認していく方法は TLE してしまいますが、bit 演算を用いればほぼ同じ考えにより高速化ができます。

std::bitset などを用いて \(j, j + 1\) の連結性を管理し、(1) のときと同様の考えで _Find_next のような \(x\) の次の \(1\) の位置を返すような関数を用いることで十分高速に答えを求めることができます。