LIS of Every Interval

Let $f(l,r)$ be the LIS length of the interval $[l,r]$.

For a fixed right endpoint $r$, define

$$d_l=f(l,r)-f(l,r-1) \qquad (1 \leq l < r).$$

Appending one element changes the LIS length by either $0$ or $1$, so every $d_l$ is $0$ or $1$.

The interval LIS matrix satisfies the following unit-Monge inequality:

$$f(l,r)+f(l+1,r-1) \leq f(l,r-1)+f(l+1,r).$$

One way to see this is to place every permutation element as a point $(i,P_i)$ and interpret an increasing subsequence as an up-right path. Two optimal paths can be uncrossed by exchanging their suffixes, which gives the inequality.

Rearranging it gives

$$f(l,r)-f(l,r-1) \leq f(l+1,r)-f(l+1,r-1).$$

Thus, for fixed $r$, the sequence $d_1,d_2,\cdots,d_{r-1}$ is nondecreasing. Since every value is either or , there is a boundary such that for and for . The case means that every is .

Assume that all answers ending at $r-1$ are already known. A query for $f(m,r)$ can be compared with the known value $f(m,r-1)$, so it tells whether is or . Therefore, the boundary can be found by binary search.

After finding $t$, compute

• $f(l,r)=f(l,r-1)$ for $l<t$,
• $$ for ,

For one right endpoint $r$, at most $\lceil\log_2 r\rceil$ queries are needed. For $N=100$, the total number of queries is

$$\sum_{r=2}^{100}\lceil\log_2 r\rceil =1+4+12+32+80+192+252 =573.$$

This is within the limit of $600$ queries.

The running time is $O(N^2)$ because all answers must be produced, and the number of queries is $O(N\log N)$.

Solution written by GPT5.6