For starters, let's sort the landmines in non-decreasing order of position. This takes ~\mathcal O(N \log N)~ time. Our primary goal will be to compute the values ~ML[i]~ and ~MR[i]~ for each mine ~i~ – the minimum and maximum positions that will be engulfed in an explosion if mine ~i~ is set off. From here, one naïve thing to try would be a straightforward simulation using breadth-first search. To compute the ~ML~ and ~MR~ of each initial mine, we can add it to the queue. Processing each mine as we pop them from the queue, we can loop through all other mines to see if that mine is set off. The simulation for each mine will take ~\mathcal O(N^2)~. For ~N~ mines, that is ~\mathcal O(N^3)~ overall. To finally process each query position ~C~, we can naively loop through all of the mines and count the number of mines that have ~ML~ and ~MR~ ranges including ~C~. Since there are at ~M~ queries, the running time for this part is ~\mathcal O(NM)~. This solution is given 15/40 of the points.

We can try certain optimizations such as gradually expanding the explosion range for each initial mine. This will get each simulation from ~\mathcal O(N^2)~ to ~\mathcal O(N)~, yielding ~\mathcal O(N^2)~ across all ~N~ mines. However, that is still too slow for ~N~ as large as ~10^6~. Furthermore, answering queries also happens to be a bottleneck, with ~M~ up to ~3 \times 10^6~. We will need to speed up both sections to sub-quadratic running time to pass under the time limit.

For a full solution, we can start by representing the mines as the nodes of a directed, unweighted graph. Let there be an edge from mine ~i~ to mine ~j~ if mine ~j~'s explosion would directly set off mine ~i~ (in other words, if ~P[j]-L[j] \le P[i] \le P[j]+R[j]~). The purpose of this graph is that ~ML[j]~ and ~MR[j]~ can be computed based on the ~ML~ and ~MR~ values of mines which have edges leading into mine ~j~ (for example, ~ML[j]~ is equal to the minimum of ~L[j]~ and the ~ML~ values of those mines).

One issue with this graph is that it can have ~\mathcal O(N^2)~ edges. However, the observation can be made that keeping at most two incoming edges for each mine ~j~ will suffice – the edge leading from the mine whose position is in the interval ~[P[j]-L[j], P[j]+R[j]]~ which has the minimum ~L~ value, and similarly the one which has the maximum ~R~ value. These (at most) two mines are clearly at least as important as any other mines that mine ~j~ can directly set off. Both of the mines can be found in ~\mathcal O(\log N)~ time by using a segment tree to perform a range minimum/maximum query on the ~L~/~R~ values of the mines.

We now have a graph with ~\mathcal O(N)~ edges which represent the relationships between the mines' ~ML~ and ~MR~ values, but it doesn't yet give us an appropriate order in which to compute these values based on one another, due to the fact that it can have cycles. If two mines are reachable from one another in this graph, they must have the same ~ML~ and ~MR~ values. As such, the next step is to locate all of the strongly connected components in the graph (in ~\mathcal O(N)~ time using an algorithm such as Tarjan's). Each strongly connected component can then be contracted to a single node, which stores the number of actual mines in the node as well as their minimum ~L~ value and maximum ~R~ value, and a new, directed acyclic graph can be created from these component nodes. In graph theory, this new graph is known as the condensation of the original, and happens to be a directed acyclic graph (DAG).

We can now perform a topological sort on the nodes of this DAG, iterating over them in order and updating each node's ~ML~ and ~MR~ values based on those of the nodes with edges leading to it. For each one, we don't need to bother looking up exactly which initial mines correspond to the component node – only how many there are that have this set of ~ML~ and ~MR~ values. This process takes ~\mathcal O(N)~ time.

Finally, we can perform a line sweep to get the requested answers. We'll need events for the civilians' positions, as well as for the start and end of each component node's final explosion range ~[ML, MR]~ (also storing the number of mines associated with this range). Upon sorting the events in ~\mathcal O((N+M) \log(N+M))~ time, we can iterate over them while maintaining the number of mines whose final explosion range affects the current position, and noting these counts each time a civilian position is reached so that they can later be outputted in the correct order.