Advanced Sequence Algorithms

Longest increasing subsequence in O(n log n), patience sorting interpretation, longest common subsequence, edit distance, sequence alignment, inversion count, order statistics, and offline dominance queries.

Patience sorting: deal cards into piles, placing each card on the leftmost pile whose top is not smaller; the number of piles equals the LIS length — exactly the tails array of Module 22.

Sequence alignment generalises edit distance with costs for matches, mismatches and gaps (Needleman–Wunsch globally, Smith–Waterman locally); Hirschberg's method recovers the alignment in linear space.

Offline dominance counting (“how many points have x ≤ X and y ≤ Y?”): sort points and queries by x, sweep, and count y values with a Fenwick tree.

Output (g++ 11.2, -std=c++17, warnings as errors, AddressSanitizer + UndefinedBehaviorSanitizer; Ubuntu 22.04 on WSL2):

#include <bits/stdc++.h>
using namespace std;

int main() {
    mt19937 rng(10);
    int n = 2000, Q = 2000, M = 1000;
    vector<pair<int, int>> pts(n); for (auto& p : pts) p = {int(rng() % M), int(rng() % M)};
    vector<array<int, 3>> qs(Q); for (int i = 0; i < Q; ++i) qs[i] = {int(rng() % M), int(rng() % M), i};
    sort(pts.begin(), pts.end());
    sort(qs.begin(), qs.end());
    vector<int> bit(M + 1, 0), ans(Q);
    auto add = [&](int i) { for (++i; i <= M; i += i & -i) ++bit[i]; };
    auto pre = [&](int i) { int s = 0; for (++i; i > 0; i -= i & -i) s += bit[i]; return s; };   // count of y <= i
    size_t p = 0;
    for (auto [X, Y, idx] : qs) {                       // sweep x: insert every point with x <= X
        while (p < pts.size() && pts[p].first <= X) add(pts[p++].second);
        ans[idx] = pre(Y);
    }
    for (auto [X, Y, idx] : qs) {
        int c = 0; for (auto [x, y] : pts) c += x <= X && y <= Y;
        if (c != ans[idx]) { cout << "mismatch\n"; return 1; }
    }
    cout << Q << " dominance queries over " << n << " points: sweep + Fenwick answers match brute force; O((n + Q) log M) vs O(nQ)\n";
}

2000 dominance queries over 2000 points: sweep + Fenwick answers match brute force; O((n + Q) log M) vs O(nQ)

Quiz

? In patience sorting, what does the number of piles equal?
+ The length of the longest increasing subsequence :: It is the size of the tails array.
- The number of inversions :: No.
- The longest decreasing run :: No.
- n / 2 :: No.

? Offline dominance counting sorts queries by x and sweeps because…
+ after inserting all points with x ≤ X, a Fenwick prefix count over y answers the query :: One dimension is handled by order, the other by the tree.
- Fenwick trees need sorted input :: Not the reason.
- queries must be answered in order :: Answers are stored by index.
- to remove duplicate points :: Unrelated.

? Edit distance versus sequence alignment?
+ Alignment generalises edit distance with arbitrary match, mismatch and gap scores :: Needleman–Wunsch, Smith–Waterman.
- They are unrelated :: Same DP shape.
- Alignment is greedy :: It is DP.
- Edit distance needs a suffix array :: No.