- アルゴリズムは3種類ある 解説
[AtCoder Beginner Contest 065 / AtCoder Regular Contest 076 D]
One natural strategy is to adapt some existing MST algorithms, and exploit the nature of problem to reduce it's time complexity. There are a lot of well known MST algorithms, such as Jarniks-Prim, or Kruskal. However, both have a serious problem — the problem makes it really hard to retrieve single edge weights. What is the workaround?
While less famous than Jarnik and Kruskal's, there is also an algorithm called Borůvka's Algorithm — the first known algorithm for Minimum Spanning Tree. In Boruvka's algorithm, all we have to do is finding a smallest outgoing edge for each component. As some kind of batch processing is allowed now, it sounds that sweep line can help. Can you see how?
In Borůvka's algorithm, we find a smallest edge leading to other components for each component, and add it to spanning tree. We will instead find a smallest outgoing edge for each node (with different component labels), which we can easily merge for a component.
We will find the smallest outgoing node from 1 to n, in order. As rectangles are events adding constant values in the interval, we can use sweep line approach — the cost of edge outgoing from node i can be maintained in a simple array with O(N) operations per query.
Now, we have to find a node with minimum edge weight, with different component origin, which can be also done in O(N) operations per nodes. Note that Borůvka's algorithm needs careful attention for edges with same costs — If there are ties, picking the one with smallest node number is a good tie-breaking rule. This leads to an O((Q + N)NlgN) time complexity, and O(N) space. It's still too slow, but it's the first algorithm with feasible space complexity.
The bottleneck is in finding minimums, and adding constant value in an interval — which hints toward a segment tree approach. If we were to find a minimum edge weight, without different component restriction, then the problem is a classical lazy propagation — we will omit the details.
To support finding minimum value with different component origin, we can slightly modify the segment tree. For each node, we record two minimums — first one gives minimum value, and second one gives minimum value among the node that have different component than first. This modification still allows lazy propagation and query exactly same as before, so we can do the whole query in O(lgN) time — the complexity is O((Q + N)lg2N). The asymptotics is not huge, but due to the high constant factor of segment tree, the solution doesn't run that fast — that's why we have a huge time limit.