As in Chapter 1, we'll simulate the entire process in reverse, processing events for adjacent platforms becoming reachable and for rock samples needing to be collected, while maintaining a disjoint-set data structure of mutually-reachable groups of platforms. The big difference is that there are now \(RC + K\) sample collection events, each of which is only applicable to a certain interval of the \(K\) situations to be evaluated, and we'll opt to simulate all \(K\) situations simultaneously.

We can no longer store a single flag per group for whether or not a robot has already been allocated to it. However, we can expand on this concept by storing the *set of situations* (out of situations \(1..K\)) for which a robot has already allocated to the group. To make this efficient, we'll represent this as a set of contiguous intervals of situation indices.

Now, when merging two groups together, the situation interval set of the resulting group should equal the union of the two existing groups' situation interval sets. The most efficient way to implement this is to have the resulting group inherit the larger of those two existing sets, with each interval in the smaller set inserted into the larger set in turn. As part of the insertion process, any overlapping intervals should get merged together.

Finally, when processing a sample collection event for platform \((i, j)\) and for sample height \(s\) (which might either be an original \(S\) value or an updated \(U\) value) which applies to the interval of situations \(a..b\), the sample cannot be collected in any situation if \(s \ge H_{i,j}\). Otherwise, it can be collected in each of the applicable situations, meaning that we should increase the sum of \(X_{1..K}\) by \(b - a + 1\). A new robot must be allocated to collect the sample in each situation \(c\) such that \(a \le c \le b\) and platform \((i, j)\)'s group's situation interval set does not include \(c\) — for each such situation, we'll need to increment the sum of \(Y_{1..K}\), and also insert \(c\) into the group's set. This is equivalent to inserting the interval \([a, b]\) into the group's set, while increasing \(Y_{1..K}\) by \(b - a + 1\) minus the total amount of overlap between that interval and any existing ones. Any existing overlapping intervals will need to get deleted/merged as part of the interval insertion process anyway, meaning that this can all be done at once.

The most expensive part of this algorithm is handling the situation interval sets. Overall, each of the \(RC + K\) sample collection events can cause at most one situation interval to get inserted into a set, each interval can be deleted at most once, and each interval can get merged into another (larger) group's set at most \(O(\log(RC))\) times. Each insertion/deletion can be performed in \(O(\log(K))\) time, resulting in an overall \(O((RC+K) \log(RC) \log(K))\) time for these operations, with the same time complexity needed for interval queries along the way.

Alternatively, the online approach described in [Chapter 3's solution](https://www.facebook.com/codingcompetitions/hacker-cup/2021/round-3/problems/D3/solution) can also be employed here.

[See David Harmeyer (SecondThread)'s solution video here.](https://youtu.be/w6Xvy0c876o?t=524)