Fitting a segment in a two-dimensional plane

I'm having troubles with the following problem

Given N x S grid and m segments parallel to the horizontal axis (all of them are tuples (x', x'', y)), answer Q online queries of form (x', x''). The answer to such a query is the smallest y (if there is one) such that we can place a segment (x', x'', y). All segments are non-overlapping yet beginning of one segment can be the ending of another i.e. segments (x', x'', y) and (x'', x''', y) are allowed. Being able to place a segment means there could exist a segment (x', x'', y) that wouldn't violate stated rules, segment isn't actually placed(board with initial segments isn't modified) but we only state there could be one.

Constraints

1 ≤ Q, S, m ≤ 10^5
1 ≤ N ≤ 10^9

Time: 1s
Memory: 256 Mb

Here is an example from the link below. Input segments are (2, 5, 1), (1, 2, 2), (4, 5, 2), (2, 3, 3), (3, 4, 3).
Answer for queries

1) (1, 2) → 1

2) (2, 3) → 2

3) (3, 4) → 2

4) (4, 5) → 3

5) (1, 3) → can't place a segment

A visualized answer for the third query (blue segment):

I don't quite understand how to approach the problem. It is supposed to be solved with persistent segment tree, but I am still unable to come up with something.

Could you help me please.

This is not my homework. The source problem can be found here http://informatics.mccme.ru/mod/statements/view3.php?chapterid=111614 . There's no English version of the statement avaliable and the test case presents input data in a different way, so don't mind the souce.

Here is an O(N log N) time solution.

Preliminaries (a good tutorial available here): segment tree, persistent segment tree.

Part 0. Original problem statement

I briefly describe the original problem statement as later I'm going to speak in its terms rather than in terms of abstract segments.

There is a train with S seats (S <= 10^5). It is known that seat s_i is occupied from time l_i to time r_i (no more than 10^5 such constraints, or passengers). Then we have to answer 10^5 queries of kind "find the lowest number of a seat with is free from time l_i to time r_i or say if there is none". All queries must be answered online, that is, you have to answer the previous query before seeing the next.

Throughout the text I denote with N both the number of seats, the number of passengers, and the number of queries, assuming they are the same order of magnitude. You can do more accurate analysis if needed.

Part 1. Answering a single query

Let's answer a query [L, R] assuming that there are no occupied places after time R. For each seat we maintain the last time when it is occupied. Call it last(S). Now the answer for the query is minimum S such that last(S) <= L. If we build a segment tree on seats then we'll be able to answer this query in O(log^2 N) time: binary search the value of S, check if range minimum on segment [0, S] is at most L.

However, it might be not enough to get Accepted. We need O(log N). Recall that each node of a segment tree stores minimum in corresponding range. We start at the root. If the minimum there is >= L then there is no available seat for such query. Otherwise either minimum in the left child or in the right child is <= L (or in both). In the first case we descend to the left child, in the second – to the right, and repeat until we reach a leaf. This leaf will correspond to the minimum seat with last(S) <= L.

Part 2. Solving the problem

We maintain a persistent tree on seats, storing last(S) for each seat (same as in the previous part). Let's process initial passengers one by one sorted by their left endpoint in increasing order. For a passenger (s_i, l_i, r_i) we update the segment tree at position s_i with value r_i. The tree is persistent, so we store the new copy somewhere.

To answer a query [L, R], find a latest version of the segment tree such that the update happened before R. If you do a binary search on versions, it takes O(log N) time.

In the version of the segment tree only passengers with their left endpoint < R are considered (even more, exactly such passengers are). So we can use the algorithm from the Part 1 to answer the query using this segment tree.