Any contiguous subsequence of floors that contains a floor with zero elevators is not reachable. Thus, we will only consider contiguous subsequences in which every floor contains at least one elevator.

Define ~E~ as the set of elevators which stop within a contiguous subsequence of floors ~[l, r]~. Notice that ~[l, r]~ is reachable if and only if starting from every elevator in ~E~, it is possible to reach all other elevators in ~E~. In other words, if we consider each floor as a set of edges between all pairs of elevators that stop at it, ~[l, r]~ is reachable if and only if ~E~ is a connected graph with edges within ~[l, r]~.

Rephrasing the question, each floor represents a set of elevators (~V_i~) and edges between elevators (~E_i~), and we want to find the largest contiguous subsequence ~[l, r]~ such that ~G = \left(\bigcup\limits_{i=l}^r V_i, \bigcup\limits_{i=l}^r E_i\right)~ contains exactly one connected component.

Observations:

• Notice that because we only care about connectivity, instead of needing ~\mathcal{O}(M^2)~ edges for each floor, we can use ~\mathcal{O}(M)~ edges, connecting each elevator on the floor to the leftmost elevator on that floor.
• Notice that starting at each floor ~l~, the connected components in ~G~ for all ~r \in [l, n]~ only changes at most ~2M-1~ times, ~M~ times for each introduced elevator, and ~M-1~ times for each edge that connects two distinct components. Thus, for each floor ~l~, there are at most ~2M-1~ important ~r~ floors where the number of connected components changes. In particular, we only care about the first time each elevator appears and the first ~M-1~ edges which connect distinct components.
• Let ~S_i~ be the first edges which connect distinct components in ~[i, n]~. Notice that ~\forall i \in [1, N-1], S_i \subseteq V_i \cup S_{i+1}~.

Algorithm:

Line sweep from ~N~ to ~1~, at each floor ~l~ maintaining:

• The earliest appearance of each elevator, in order of appearance. This can be done by adding the elevators which appear on floor ~l~ at the front of the list and then removing duplicates, taking ~\mathcal{O}(M)~ time.
• The first ~M-1~ edges which connect distinct components. As ~V_l, S_{l+1}~ each contains at most ~M~ edges, we can just create a new DSU and add all of the edges in order, noting the edges which connect distinct components, taking ~\mathcal{O}(M*\alpha(M))~ time.

Then at each floor, add the important edges and elevators to a DSU in order. If at any point ~G~ contains only one connected component, the ~r~ floors after the current update and before the next update creates a reachable contiguous subsequence with ~l~ and thus should be considered in the final answer. In total, this takes ~\mathcal{O}(M*\alpha(M))~ time.

Note: Special care should be taken for floors with zero elevators so that we don't consider contiguous subsequences which include them.

Time Complexity: ~\mathcal{O}(NM*\alpha(M))~