xv. Range LIS

Answer “length of the longest strictly increasing subsequence of $a[l..r)$” for many ranges. One kernel array $K$ of length $n$ answers every range:

$\text{LIS}(a[l..r))=(r-l)-\#\{j\in [l,r):K_j<r\}.$

$K$ is computed in $O(n{\log }^{2}n)$ via seaweed combing and the unit-Monge (sticky braid) product. Queries are then 2D dominance counts: offline sweep + Fenwick in $O(\log n)$, or online with a wavelet matrix (count $j\ge l$ with $K_j<r$; note $K_j\ge j$ always).

Simpler cases first:

• few queries: patience sorting per query, $O((r-l)\log n)$ (LIS, LCS and Edit Distance);
• all prefixes or all suffixes: one patience sort;
• queries with fixed $l$: sweep $r$ with one patience sort from $l$;
• small values ($a_i\le 50$): segment tree storing a $V\times V$ table “LIS using values in $[x,y]$”, merged in $O(V^3)$ or $O(V^2)$ with monotone tricks.

Seaweeds

LIS of $a[l..r)$ is the LCS of $a[l..r)$ with the sorted list of distinct values (strict) or of all values with ties broken right-to-left (strict) / left-to-right (non-strict). Reduce to a permutation $p$ by ranking values, then draw the $n\times n$ grid: rows = values (top to bottom: increasing), columns = positions. Cell $(v,j)$ is a match iff $p_j=v$.

Send a strand (seaweed) into the top of every column and into the left of every row. In each cell, two strands meet: one going down, one going right.

• At a match cell they bounce: the strand from the top leaves through the right side, the strand from the left leaves through the bottom.
• At a mismatch cell they cross (the top strand continues down, the left strand continues right), unless the two strands have already crossed earlier, in which case they bounce.

$K_j$ is the column where the strand that entered column $j$ from the top leaves the bottom, or $n$ if it leaves through the right side.

Proof sketch: why the formula holds

This is Tiskin’s semi-local LCS theory. For the grid of $X$ (rows) versus $Y$ (columns), the semi-local score $H(l,r)=\text{LCS}(X,Y[l..r))$ satisfies $H(l,r)=(r-l)-\#\{$strands entering the top in $[l,r)$ and leaving the bottom in $[l,r)\}$. The idea: a combed strand going from the top of column $j$ straight to the bottom of a column $<r$ within the window corresponds to a column of $Y[l..r)$ that is “skipped” by every optimal alignment. Formally, the distance matrix $(r-l)-H(l,r)$ is a unit-Monge matrix, its density (the cross-differences) is a permutation matrix, and the combing procedure computes exactly that permutation: the local rule “bounce at matches, cross once at mismatches” is the min-plus update of the DP $H$ written in terms of these permutations. The “already crossed” rule is what makes the composition of cells the sticky (Hecke / 0-Hecke monoid) product rather than ordinary permutation composition. For $X$ = the sorted values, LCS with $X$ is exactly the LIS, giving the formula. Strands entering column $j$ can only move right or down, so $K_j\ge j$.

Fast combing via the sticky product

Combing cell by cell is $O(n^2)$. Faster: split the values into the lower half and the upper half. Each half is a strip of rows; the columns whose value is in the other half are just straight vertical strands in that strip. Comb each strip recursively (as a permutation of half the size), lift the result to a braid on $2n$ strands, and multiply the two braids with the sticky product (the unit-Monge distance product, min-plus product of the corresponding Monge matrices), which the steady ant algorithm computes in $O(N\log N)$. Total $O(n{\log }^{2}n)$, about 0.6 s at $n=10^5$.

Proof sketch: steady ant

The sticky product $c=a\odot b$ of permutations corresponds to the min-plus product of their unit-Monge distance matrices $D_c(i,k)={\min }_j(D_a(i,j)+D_b(j,k))$. Split $b$‘s middle index into a low half and a high half: $D_c=\min (F_{\text{lo}},F_{\text{hi}})$ where each $F$ is computed recursively from half-size products. The difference $\delta (i,k)=F_{\text{hi}}(i,k)-F_{\text{lo}}(i,k)$ is monotone in both $i$ and $k$ (a consequence of the Monge property), so the region where the low half wins is bounded by a monotone staircase. Away from the staircase, $c$ coincides with the corresponding half’s points; along it, at most $O(N)$ cells are inspected while walking the staircase once. Hence $T(N)=2T(N/2)+O(N)=O(N\log N)$.

Implementation

// c = a then b as sticky braids, permutations of length N, O(N log N). pool: scratch of 24 N ints.
void stickyRec(const int* a, const int* b, int N, int* c, int* pool) {
    if (N == 1) { c[0] = 0; return; }
    int h = N / 2, m = N - h;
    int *aLoRows = pool, *aHiRows = aLoRows + h, *rk = aHiRows + m, *loCols = rk + N, *hiCols = loCols + h;
    int *aLo = hiCols + m, *aHi = aLo + h, *bLo = aHi + m, *bHi = bLo + h, *cLo = bHi + m, *cHi = cLo + h;
    int *rowCol = cHi + m, *colRow = rowCol + N, *bnd = colRow + N, *dAt = bnd + N + 1, *rest = dAt + N + 1;
    int nl = 0, nh = 0;
    for (int i = 0; i < N; i++) (a[i] < h ? aLoRows[nl++] : aHiRows[nh++]) = i;
    for (int k = 0; k < N; k++) rk[k] = -1;
    for (int j = 0; j < h; j++) rk[b[j]] = 0;
    nl = nh = 0;
    for (int k = 0; k < N; k++) { if (rk[k] == 0) rk[k] = nl, loCols[nl++] = k; else rk[k] = nh, hiCols[nh++] = k; }
    for (int t = 0; t < h; t++) aLo[t] = a[aLoRows[t]], bLo[t] = rk[b[t]];
    for (int t = 0; t < m; t++) aHi[t] = a[aHiRows[t]] - h, bHi[t] = rk[b[t + h]];
    stickyRec(aLo, bLo, h, cLo, rest);
    stickyRec(aHi, bHi, m, cHi, rest);
    for (int t = 0; t < h; t++) { int r = aLoRows[t], col = loCols[cLo[t]]; rowCol[r] = col, colRow[col] = r; }
    for (int t = 0; t < m; t++) { int r = aHiRows[t], col = hiCols[cHi[t]]; rowCol[r] = ~col, colRow[col] = ~r; }
    // delta(i, k) = #{high: row < i, col < k} - #{low: row >= i, col >= k}, monotone in i and k
    auto colStep = [&](int k, int r) { return colRow[k] < 0 ? ~colRow[k] < r : colRow[k] >= r; };
    auto rowStep = [&](int i, int k) { return rowCol[i] < 0 ? ~rowCol[i] < k : rowCol[i] >= k; };
    int k = 0, d = 0; bnd[N] = 0, dAt[N] = 0;
    for (int i = N - 1; i >= 0; i--) {                          // bnd[i] = first k with delta(i, k) >= 0
        d -= rowStep(i, k);
        while (d < 0) d += colStep(k, i), k++;
        bnd[i] = k, dAt[i] = d;
    }
    for (int i = 0; i < N; i++) {
        int kb = bnd[i + 1], ks = max(kb - 1, 0), own = rowCol[i];
        int e1 = kb >= 1 ? dAt[i + 1] - colStep(kb - 1, i + 1) : dAt[i + 1];
        int e0 = e1 - rowStep(i, ks);
        c[i] = -1;
        for (int x = ks; x < bnd[i]; x++) {                     // cells along the staircase
            int n1 = e1 + colStep(x, i + 1), n0 = e0 + colStep(x, i);
            if ((own == ~x) + min(n0, 0) - min(e0, 0) - min(n1, 0) + min(e1, 0) == 1) c[i] = x;
            e1 = n1, e0 = n0;
        }
        if (c[i] == -1) c[i] = own >= 0 ? own : ~own;            // away from the staircase the half keeps its point
    }
}
vector<int> stickyProduct(const vector<int>& a, const vector<int>& b) {
    int N = sz(a); vector<int> c(N), pool(24 * N + 64);
    if (N) stickyRec(a.data(), b.data(), N, c.data(), pool.data());
    return c;
}
// braid of permutation p on 2n strands. starts: s < n = left end of row n-1-s, s >= n = top of column s-n.
// ends: e < n = bottom of column e, e >= n = right end of row 2n-1-e.
vector<int> seaweedBraid(const vector<int>& p) {
    int n = sz(p);
    if (n == 0) return {};
    if (n == 1) return {0, 1};
    int h = n / 2, m = n - h;
    vector<int> colsLo, colsHi, qLo, qHi, idxLo(n, -1), idxHi(n, -1);
    for (int i = 0; i < n; i++) {
        if (p[i] < h) idxLo[i] = sz(colsLo), colsLo.push_back(i), qLo.push_back(p[i]);
        else idxHi[i] = sz(colsHi), colsHi.push_back(i), qHi.push_back(p[i] - h);
    }
    vector<int> bLo = seaweedBraid(qLo), bHi = seaweedBraid(qHi), top(2 * n), bot(2 * n);
    auto topEnd = [&](int e) { return e < h ? m + colsLo[e] : 2 * n - 2 * h + e; };
    auto botEnd = [&](int e) { return e < m ? colsHi[e] : n - m + e; };
    for (int s = 0; s < m; s++) top[s] = s;
    for (int s = m; s < n; s++) top[s] = topEnd(bLo[s - m]);
    for (int c = 0; c < n; c++) top[n + c] = idxLo[c] < 0 ? m + c : topEnd(bLo[h + idxLo[c]]);
    for (int s = 0; s < m; s++) bot[s] = botEnd(bHi[s]);
    for (int c = 0; c < n; c++) bot[m + c] = idxHi[c] < 0 ? c : botEnd(bHi[m + idxHi[c]]);
    for (int s = 2 * n - h; s < 2 * n; s++) bot[s] = s;
    return stickyProduct(top, bot);
}
template<class T> struct RangeLIS {
    int n; vector<int> K;
    RangeLIS(const vector<T>& a, bool strict = true) : n(sz(a)), K(n) {
        vector<int> ord(n), p(n); iota(all(ord), 0);
        stable_sort(all(ord), [&](int i, int j) { return a[i] != a[j] ? a[i] < a[j] : strict ? i > j : i < j; });
        for (int r = 0; r < n; r++) p[ord[r]] = r;
        vector<int> br = seaweedBraid(p);
        for (int j = 0; j < n; j++) K[j] = br[n + j] < n ? br[n + j] : n;
    }
    vector<int> query(const vector<pair<int, int>>& qs) const {   // offline, [l, r)
        vector<vector<int>> byR(n + 1), atK(n + 1);
        for (int i = 0; i < sz(qs); i++) byR[qs[i].second].push_back(i);
        for (int j = 0; j < n; j++) atK[K[j]].push_back(j);
        Fenwick<int> fw(n); vector<int> res(sz(qs));
        for (int r = 0; r <= n; r++) {
            if (r) for (int j : atK[r - 1]) fw.add(j, 1);           // now holds all j with K[j] < r
            for (int i : byR[r]) { auto [l, rr] = qs[i]; res[i] = (rr - l) - fw.sum(l, n); }
        }
        return res;
    }
};

Ties: for strictly increasing, equal values are ranked right-to-left, so two equal values can never both be in an increasing chain; for non-decreasing, left-to-right so they always can. Library Checker “Static Range LIS Query”.

Related

• Semi-local LCS of two strings (LCS of $s$ with every substring of $t$) uses the same seaweed kernel; combing a $|s|\times |t|$ grid directly costs $O(|s||t|)$ and gives all $O(|t{|}^2)$ answers implicitly (Other Pattern Matching).
• Unit-Monge product in general: the min-plus product of two $n\times n$ unit-Monge matrices in $O(n\log n)$; also used for range LCS queries, “longest increasing subsequence in a cyclic shift”, and merging DP over strings.