PROBLEM LINK:
Author: Sergey Kulik
Tester: Kamil Debowski
Editorialist: Pawel Kacprzak
DIFFICULTY:
MEDIUM-HARD
PREREQUISITES:
Segment tree
PROBLEM:
For a given 1-D grid with N points numbered from 1 to N from left to right, the task is to handle Q queries. A query can either mark an unmarked point on the grid or add a segment to the grid. We say that a segment [L, R] is active if and only if all grid points it contains are marked. More precisely, each query is of one of two below types:
-
mark(P): marks point P, which is guaranteed to be not marked before. The answer for this query is the number of segments on the grid which becomes active just after marking P.
-
add(L, R): adds segment with left endpoint in L and right endpoint in R to the grid
An important thing here is that all queries have to be handled online, which means that a single query has to be handled before reading the next query from the input. If this is not the case, one can try some solutions taking advantage of the fact that all queries can be for example grouped somehow and then answered in batches.
QUICK EXPLANATION:
Keep track of not yet active segments using a data structure like a segment tree. Observe that if P is the point to mark and x is the first not marked point to the left of P and y is the first not marked point to the right of P, then all not yet active segments with left endpoint in range [x+1, P] and right endpoint in range [P, y-1] will become active. Use underlying data structure to find them and remove one by one as they all become active now.
EXPLANATION:
The \textbf{main observation} is that can be used to solve each subtask is that if P is the point to mark in a query, x is the first not marked point to the left of P, and y is the first not marked point to the right of P, then all not yet active segments with left endpoint in range [x+1, P] and right endpoint in range [P, y-1] will become active.
Approaches for a given subtask differ in the method of finding points x and y defined above as well as in a way of managing the set of not yet activated segments.
Subtask 1
In the first subtask both N and Q are at most 10^4, so one can use the most straightforward approach based on the main observation. A simple array can be used to mark points explicitly as well as a simple list can be used to keep track of all not yet activated segments. When trying to find the number of segments activated just after marking point P, one can simply iterate over the array of marked points to find x and y defined in the main observation and then iterate over the list of all not yet activated segments to find the ones with both endpoints in appropriate ranges. This solution has time complexity O(Q \cdot (N+Q)) because for each query we iterate over O(N) points on the grid and also over O(Q) not yet activated segments.
Subtask 2
In the second subtask, N and Q can be at most 10^5, so the straightforward method used in the first subtask is too slow. Constraints here are chosen for a slower implementation of the intended solution for the last subtask or in general methods with O(\log^2 (N+Q)) time complexity for a single query.
Subtask 3
In the last subtask both N and Q can be up to 10^6, so we need a really fast solution. Let’s recall the main observation once more:
If P is the point to mark in a query, x is the first not marked point to the left of P, and y is the first not marked point to the right of P, then all not yet active segments with left endpoint in range [x+1, P] and right endpoint in range [P, y-1] will become active.
In order to use the observation to solve this subtask, we have to deal with two things.
The first one is how to find points x and y for a given point P fast enough. Perhaps the simplest method is to keep track a sorted set Z of not yet marked points (initially all point are there) and for a given P use binary search to find x as the maximum point in Z smaller than P and y as the minimum point in Z greater than P. In \texttt{C++} one can use std::set to store Z and use very useful set::lower_bound function to find both these point using only library functions.
The second thing is how to keep track of not yet activated segments in such a way that we can easily delete them as well as find all segments with left endpoint in a range [x+1, P] and right endpoint in [P, y-1]. One possibility is to use a variation of a segment tree S here. The idea is that in a leaf of S corresponding to point K, we store a sorted list of right endpoints of segments with left endpoint in K, while in internal node of S corresponding to some range [L, R], we store the minimum right endpoint of all segments with left endpoints in [L, R]. Notice that a value of any internal node is defined by values stored in its children, whenever they are internal nodes or leaves.
Putting all together, whenever we add a segment we simply add it to S. When we mark point P, we first find ranges A = [x+1, P] and B = [P, y-1]. Then, while the minimum right endpoint of a segment with its left endpoint in A is in B, then we add this segment to the answer and remove it from S as it becomes active. One important thing to notice is that the minimum right point of not yet activated segment with left endpoint in A cannot be smaller than P, because otherwise, it would have all its grid point marked already, so only segments becoming active now are counted that way. Finally, we mark point P and proceed to the next query.
The time complexity of this method is O(Q \cdot \log (N+Q)) - notice that each segment is inserted to S exactly once and removed also only once from S. For implementation details please refer to author’s and tester’s solutions linked below.
AUTHOR’S AND TESTER’S SOLUTIONS:
Setter’s solution can be found here.
Tester’s solution can be found here.