Initial Transformation

A useful reformulation of this interval connectivity problem is to consider pairs of adjacent vertices.

For each pair of adjacent vertices \(i\) and \(i+1\), let \(vl_i\) and \(vr_i\) denote the minimum and maximum vertex indices, respectively, along the path between them. Then, the two vertices are connected in the subgraph induced by an interval \([L,R]\) if and only if the entire path between them lies within that interval. Equivalently, we must have

\[ L\le vl_i\quad\text{and}\quad vr_i\le R. \]

We can compute all \(vl_i\) and \(vr_i\) values in \(O(n\log n)\) time using Heavy-Light Decomposition (HLD) and a Sparse Table.

Consequently, an interval \([L,R]\) is good if and only if

\[ L=\min_{L\le i<R}vl_i,\qquad R=\max_{L\le i<R}vr_i. \]

This characterization leads to an \(O(n^2)\) solution.

Analysis

The case \(L=R\) must be handled separately, since the range \([L,R)\) is empty in this case.

To maintain historical sums, we can use a sweep-line approach, processing the right endpoint \(r\) in increasing order.

When processing \(r\), first set \(val_{r-1}=1\), marking \(r-1\) as a candidate left endpoint.

Next, set all \(val\) values in the range \([vl_{r-1}+1,r)\) to \(0\), eliminating these positions as candidates for the current left endpoint. However, their previously accumulated contributions in the segment tree must be preserved.

After these updates, every position \(L\) with \(val_L=1\) satisfies

\[ L=\min_{L\le i<r}vl_i, \]

where the current right endpoint is \(r\).

We must now enforce the second condition:

\[ r=\max_{L\le i<r}vr_i. \]

Observe that \(\max_{L\le i<r}vr_i\) is non-increasing as \(L\) increases.

Maintain a monotonic stack over the \(vr_i\) values. At this point, \(vr_{r-1}\ge r\). The smallest valid left endpoint either does not exist or is one greater than the index associated with the second element from the top of the stack. This boundary follows from the ordering maintained by the stack, with the precise interpretation depending on how indices and equal values are handled in the implementation.

For the resulting range of valid left endpoints, accumulate the current \(val\) values into the historical sums stored in the segment tree, and update the variable sum accordingly. Here, sum denotes the historical sum maintained by the segment tree.

To answer a query, perform a range-sum query on the historical sums for the corresponding right endpoint.

Complexity Analysis

• Time complexity: \(O((n+q)\log n)\).
• Space complexity: \(O(n\log n)\).

The key to this solution is to combine the interval characterization with a sweep line, a monotonic stack, and a segment tree that maintains historical sums. Once these observations are established, the implementation follows naturally.Reference implementation.

The above content was translated from Chinese to English by ChatGPT.