Since the graph in this problem may have up to \(NQ\) edges, one cannot directly apply an algorithm that determines the minimum spanning tree of a general graph.

We will try to exploit the special form of the graph to optimize Kruskal’s algorithm against it.

We first sort the edges by their costs and appropriately reassign indices so that \(C_1 \leq C_2 \leq \ldots \leq C_Q\). (In actual implementation, you probably do not need to actually reassign them.)

According to Kruskal’s algorithm, one can determine the minimum spanning tree as follows:

• Prepare an \((N + Q)\)-vertex graph without an edge.
• For \(i = 1, 2, \ldots ,Q\) in order:
  • For each \(j = L_i, L_i + 1, \ldots, R_i\) in order, add an edge between vertices \((N + i)\) and \(j\) of cost \(C_i\) if and only if vertices \((N + i)\) and \(j\) are not connected.

While it is still difficult to handle the conditions, one can notice that vertices \((N + i)\) and \(j\) are always disconnected if \(j =L_i\), and that vertices \((N + i)\) and \((j - 1)\) are connected if and only if vertices \((j - 1)\) and \(j\) are, in order to realize that it is sufficient to perform connectivity check for vertices with adjacent indices: \(j - 1\) and \(j\). Also, the graph is disconnected if and only if there exists an integer \(j\) between \(1\) and \((N-1)\) (inclusive) such that vertices \((j - 1)\) and \(j\) are disconnected.

Naively implementing this still costs \(\Theta(NQ + Q\log Q)\), but now that the problem is simplified, there are various approaches.

We introduce three examples.

(1) Use a set (or similar data structure)

Manage the set of \(1 \leq j < N\) such that vertices \((j - 1)\) and \(j\) are disconnected in a data structure like std::set in C++, and remove those among \(L_i, L_i + 1, \ldots, R_i - 1\) that is not in the set. Naively checking the existence for each element still leads to TLE, but one can use a function such as lower_bound in std::set that retrieves the minimum element greater than or equal to \(x\), as removal of an element occurs at most \((N - 1)\) times and the complexity is bounded by \(O((N + Q) \log N)\), which is fast enough.

(2) Use a lazy segment tree

One can also use a lazy segment tree that supports segment-sum retrieval and segment-filling with \(0\). The \(j\)-th element of the lazy segment tree should be \(0\) if vertices \(j\) and \((j+1)\) are connected, and \(1\) otherwise. Initialize such a segment tree of length \((N-1)\) all with \(1\); then the number of edges connecting vertex \(N + i\) and any of vertices \(L_i + 1, L_i + 2, \ldots, R_i\) can be retrieved as the segment sum of \([L_i, R_i)\), and adding an edge is fulfilled by filling \([L_i, R_i)\) with \(0\).

(3) Use bitwise operations

While a naive scan-based algorithm on an array results in TLE (Time Limit Exceeded), one can make use of bitwise operations with almost the same idea.

The answer can be found fast enough by managing connectivity for each \((j, j+1)\) using std::bitset and using a function that returns the next position of \(1\) in the same way as _Find_next in (1), the answer can be fond enough.