排列的最长公共子序列

📘 题目描述

给定两个 $1\sim n$ 的排列 $s,t$，求出它们的 最长公共子序列 长度，其中 $n \leq 2 \cdot 10^5$。

---

💡 解题思路

⚠️ 朴素解法只能得 50 分

使用传统的 DP（$O(n^2)$）算法求解 LCS（最长公共子序列）在本题中由于数据范围过大，会超时，仅能通过部分数据。

---

✅ 利用排列的特殊性质优化

由于 $s$ 和 $t$ 是 $1 \sim n$ 的排列（元素唯一且无重复），可以通过映射转换问题为 LIS（最长上升子序列）问题：

✨ 映射核心思想

• 将 $s$ 中的每个值映射为其下标位置，构造出一个“位置数组” $a$：
• 即：a[s[i]] = i，表示数值 s[i] 在第 i 个位置
• 接着把 $t$ 中的每个元素 t[i] 替换为它在 $s$ 中的位置，即 t[i] = a[t[i]]

这样处理后：

• 映射后的 $t$ 实际上表示的是：原排列 $t$ 中的元素在排列 $s$ 中的顺序
• 因此，在映射后的 $t$ 中寻找最长上升子序列，其长度就是原始两个排列 $s$ 和 $t$ 的最长公共子序列长度

---

🧪 举个例子

原始输入：

• s = [3, 2, 1]
• t = [1, 3, 2]

执行映射操作：

for (int i = 1; i <= n; i++) 
{
    a[s[i]] = i;      // s[i] 映射为 i
}
for (int i = 1; i <= n; i++) 
{
    t[i] = a[t[i]];   // t[i] 替换为其在 s 中的位置
}

映射结果：

• s = [1, 2, 3]
• t = [3, 1, 2]

此时只需在 $t$ 中求 LIS，答案为 $2$（对应的是公共子序列 [3, 2]）。

✅ 总结

为了求两个排列的最长公共子序列（LCS），我们可以：

• 将排列 $s$ 中的值映射为其下标位置；

• 按照这个映射，转换 $t$ 中的每一个元素；

• 在新转换后的 $t$ 上，使用二分 + 贪心算法求最长上升子序列（LIS）长度；

• 答案即为 LIS 长度，也就是原始 $s$ 和 $t$ 的 LCS 长度。

⏱️ 时间复杂度分析

• 映射操作：$O(n)$
• 求 LIS：$O(n \log n)$

最终总时间复杂度为 $O(n \log n)$，可以通过所有数据。

✅ 代码实现

for (int i = 1; i <= n; i++) 
{
    a[s[i]] = i;      // s[i] 映射为 i
}
for (int i = 1; i <= n; i++) 
{
    t[i] = a[t[i]];   // t[i] 替换为其在 s 中的位置
}

// 下面开始对 t 求 LIS 即可

for (int i = 1; i <= n; i++)
{
    if (t[i] > d[len])
    {
        d[++len] = t[i];
    }
    else
    {
        int pos = lower_bound(d + 1, d + len + 1, t[i]) - d;
        d[pos] = t[i];
    }
}

// 答案为 len 的值