  In this work, we present a plethora of results for the range longest
increasing subsequence problem (Range-LIS) and its variants. The input to
Range-LIS is a sequence $\mathcal{S}$ of $n$ real numbers and a collection
$\mathcal{Q}$ of $m$ query ranges and for each query in $\mathcal{Q}$, the goal
is to report the LIS of the sequence $\mathcal{S}$ restricted to that query.
Our two main results are for the following generalizations of the Range-LIS
problem:
  $\bullet$ 2D Range Queries: In this variant of the Range-LIS problem, each
query is a pair of ranges, one of indices and the other of values, and we
provide an algorithm with running time $\tilde{O}(mn^{1/2}+ n^{3/2} +k)$, where
$k$ is the cumulative length of the $m$ output subsequences. This breaks the
quadratic barrier of $\tilde{O}(mn)$ when $m=\Omega(\sqrt{n})$. Previously, the
only known result breaking the quadratic barrier was of Tiskin [SODA'10] which
could only handle 1D range queries (i.e., each query was a range of indices)
and also just outputted the length of the LIS (instead of reporting the
subsequence achieving that length).
  $\bullet$ Colored Sequences: In this variant of the Range-LIS problem, each
element in $\mathcal{S}$ is colored and for each query in $\mathcal{Q}$, the
goal is to report a monochromatic LIS contained in the sequence $\mathcal{S}$
restricted to that query. For 2D queries, we provide an algorithm for this
colored version with running time $\tilde{O}(mn^{2/3}+ n^{5/3} +k)$. Moreover,
for 1D queries, we provide an improved algorithm with running time
$\tilde{O}(mn^{1/2}+ n^{3/2} +k)$. Thus, we again break the quadratic barrier
of $\tilde{O}(mn)$. Additionally, we prove that assuming the well-known
Combinatorial Boolean Matrix Multiplication Hypothesis, that the runtime for 1D
queries is essentially tight for combinatorial algorithms.
