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.

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

Problems

Relating to LIS: