title: Fitting a segment in a two-dimensional plane
body: <p>I'm having troubles with the following problem</p>
  
  <blockquote>
    <p>Given <em>N x S</em> grid and <em>m</em> segments parallel to the horizontal axis (all of them are tuples <em>(x', x'', y)</em>), answer <em>Q</em> online queries of form <em>(x', x'')</em>. The answer to such a query is the smallest <em>y</em> (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.</p>
  </blockquote>
  
  <p>Constraints </p>
  
  <pre><code>1 ≤ Q, S, m ≤ 10^5
  1 ≤ N ≤ 10^9
  
  Time: 1s
  Memory: 256 Mb
  </code></pre>
  
  <p><a href="https://i.stack.imgur.com/c2uFA.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/c2uFA.png" alt="enter image description here"></a></p>
  
  <p>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).<br>
  Answer for queries </p>
  
  <p>1) (1, 2)  → 1</p>
  
  <p>2) (2, 3)  → 2</p>
  
  <p>3) (3, 4)  → 2</p>
  
  <p>4) (4, 5)  → 3</p>
  
  <p>5) (1, 3)  → can't place a segment</p>
  
  <p>A visualized answer for the third query (blue segment):</p>
  
  <p><a href="https://i.stack.imgur.com/ReQsU.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/ReQsU.png" alt="A visualized answer for the third query"></a></p>
  
  <p>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.</p>
  
  <p>Could you help me please.</p>
  
  <p>This is not my homework. The source problem can be found here <a href="http://informatics.mccme.ru/mod/statements/view3.php?chapterid=111614" rel="nofollow noreferrer">http://informatics.mccme.ru/mod/statements/view3.php?chapterid=111614</a> . 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.</p>