Typical ICPC Problem#12869

Typical ICPC Problem (Editorial)

For a tree, it's a pretty well-known problem, but let's remind the solution.

Let's process the nodes in order from the smallest weight to the largest, keeping the current right end . For each node with weight from to , we will also keep the value , which is r-i+1 - the number of edges whose both ends have weights in range . Then, the range [l, r] will be good if and only if will be equal to when we processed all nodes with weight up to .

It's easy to update all the values when moving from to r+1: we just have to add/subtract on some segments. Also note that all numbers are always at least , and just have to return the number of ones. This hints to the segment tree solution, which allows queries of adding on subsegment, finding minimum on subsegment, and finding the number of minimums.

But it's not a tree, it's a CACTUS!!! How to deal with this case then?

In the tree case, we used that a forest is connected iff the number of nodes number of edges is precisely . In the cactus case, we have something similar: cactus is connected iff the number of nodes number of edges + number of cycles is precisely . So, the algorithm would be to do the following: determine all edge cycles, which are luckily disjoint, for each of them determine the largest and smallest weight of a node, and when we are processing nodes in the same order of weight, add on prefix when becomes equal to the largest weight on the cycle.