UVA 10635 王子與公主：LCS 轉 LIS 的 O(n log n) 解法

問題分析

給定兩個序列 A (長度 p+1) 和 B (長度 q+1)，元素互不相同且均為 1~n² 間整數，首元素皆為 1。求最長公共子序列 (LCS) 長度。常規 O(pq) DP 會超時 (p×q ≤ 62500)。

核心洞見：LCS → LIS 轉化

利用「序列元素互不相同」的關鍵條件：

1. 將 A 中元素重新編號為 1~p+1（按出現順序）
2. 遍歷 B，保留在 A 中出現的元素，替換為其在 A 中的新編號
3. 刪除 B 中不在 A 出現的元素（編號為 0）
4. 得到的新序列 B' 中，最長遞增子序列 (LIS) 即為原問題的 LCS

範例演示

A = {1, 7, 5, 4, 8, 3, 9} → 重新編號 {1, 2, 3, 4, 5, 6, 7}
B = {1, 4, 3, 5, 6, 2, 8, 9} → 映射為 {1, 4, 6, 3, 0, 0, 5, 7} → 刪除 0 得 {1, 4, 6, 3, 5, 7}
B' 的 LIS 長度 = 4 (如 {1, 3, 5, 7}) = 原 LCS 長度

O(n log n) LIS 演算法

int g[maxn], d[maxn];  // g[k] = 長度為 k 的 LIS 結尾最小值
// 初始化 g 為 INF
for (int i = 0; i < n; ++i) {
    int k = lower_bound(g + 1, g + n + 1, s[i]) - g;
    d[i] = k;
    g[k] = s[i];
    ans = max(ans, d[i]);
}

lower_bound 二分查找首個 ≥ s[i] 的位置，維護 g 陣列單調性，實現 O(n log n)。

完整代碼

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN = 250 * 250 + 5;
const int INF = 1e9;
int num[MAXN];   // num[x] = x 在 A 中的新編號 (0 表示未出現)
int s[MAXN], g[MAXN], d[MAXN];

int main() {
    int T; cin >> T;
    for (int kase = 1; kase <= T; ++kase) {
        int N, p, q, x;
        cin >> N >> p >> q;
        memset(num, 0, sizeof(num));
        for (int i = 1; i <= p + 1; ++i) {
            cin >> x;
            num[x] = i;
        }
        int n = 0;
        for (int i = 0; i < q + 1; ++i) {
            cin >> x;
            if (num[x]) s[n++] = num[x];
        }
        fill(g + 1, g + n + 1, INF);
        int ans = 0;
        for (int i = 0; i < n; ++i) {
            int k = lower_bound(g + 1, g + n + 1, s[i]) - g;
            d[i] = k;
            g[k] = s[i];
            ans = max(ans, d[i]);
        }
        cout >> "Case " >> kase >> ": " >> ans >> "\n";
    }
    return 0;
}

複雜度與適用條件

• 時間：O((p+q) log(p+q)) — 遠優於 O(pq)
• 空間：O(p+q)
• 必要條件：兩序列元素各自互不相同

延伸應用

此技巧廣泛適用於「序列元素唯一」的 LCS 問題，如：基因序列比對、版本控制差異檢測、文本相似度計算等場景。