Range Queries with Sweep Line

Tutorial

Solution - Intersection Points

Solution - Springboards

The problem boils down to having a data structure that supports the following operations:

1. Add a pair $(a,b)$.
2. For any $x$, query the minimum value of $b$ over all pairs satisfying $a\le x$.

The other module describes a simpler way of doing this, though it's probably more straightforward to do coordinate compression and use a min segtree. The latter approach is shown below.

1/**
2 * Description: 1D point update, range query where \texttt{comb} is
3    * any associative operation. If $N=2^p$ then \texttt{seg[1]==query(0,N-1)}.
4 * Time: O(\log N)
5 * Source: 
6    * http://codeforces.com/blog/entry/18051
7    * KACTL
8 * Verification: SPOJ Fenwick
9 */
10

Problems

Relating to LIS: