你好，同学。今天我们要攻克的是 P1439 最长公共子序列 (LCS)。

这道题在 NOI 竞赛中极具代表性，因为它不仅考查了基础的 二维 DP，更考查了问题的转化能力（将 LCS 转化为 LIS）。你之前的成绩单显示你在“字符相等时的转移来源”上有疏漏，这道题将通过大数据的压力，逼迫你从本质上理解状态的依赖关系。

---

第一部分：NOI 规范题面

【题目描述】

给出 $1, 2, \ldots, n$ 的两个排列 $P_1$ 和 $P_2$。所谓排列，是指 $1$ 到 $n$ 中的每个数字在序列中恰好出现一次。求这两个序列的最长公共子序列（Longest Common Subsequence）的长度。

【输入格式】

第一行是一个整数 $n$。 接下来两行，每行为 $n$ 个数，分别为 $P_1$ 和 $P_2$。

【输出格式】

一个整数，表示最长公共子序列的长度。

【输入输出样例 #1】

输入 #1

5 
3 2 1 4 5
1 2 3 4 5

输出 #1

3

【数据规模与约定】

• 对于 $50\%$ 的数据，$n \le 10^3$。
• 对于 $100\%$ 的数据，$n \le 10^5$。
• 时间限制：$1.0 \text{s}$，内存限制：$128 \text{MB}$。

---

第二部分：预备知识点

1. 基础 LCS 状态转移：理解 $O(n^2)$ 的转移方程。
2. 排列的离散化映射：利用“排列”中元素互异且对称的特性进行映射。
3. 最长递增子序列 (LIS)：掌握 $O(n \log n)$ 的贪心+二分优化算法。
4. 模型转化：理解为什么“两个排列的 LCS”可以等价于“一个排列的 LIS”。

---

第三部分：启发式思维引导（草稿纸上的推理）

请拿出一张草稿纸，跟我一起进行思维演进：

1. 为什么常规 DP 会死？

你已经掌握了 $O(n^2)$ 的方程：

• 若 $P_1[i] == P_2[j]$，则 dp[i][j] = dp[i-1][j-1] + 1
• 否则 dp[i][j] = max(dp[i-1][j], dp[i][j-1]) 思考：当 $n=10^5$ 时，$n^2 = 10^{10}$。无论时间还是空间（约 40GB）都会爆炸。

2. 排列的“独特性”在哪里？

观察：两个序列里数字都是 $1 \sim n$。 启发：如果我们把 $P_1$ 重新定义为“标准顺序”，会发生什么？

• 假设 $P_1 = \{3, 2, 1, 4, 5\}$。
• 我们建立一个映射 map：map[3]=1, map[2]=2, map[1]=3, map[4]=4, map[5]=5。
• 此时 $P_1$ 在我们眼里变成了 $\{1, 2, 3, 4, 5\}$（它是单调递增的！）。
• 将 $P_2 = \{1, 2, 3, 4, 5\}$ 按照同样的映射转换，得到 $P_2' = \{3, 2, 1, 4, 5\}$。

3. 核心转化

结论：在 $P_1$ 已经变成升序的情况下，任何 $P_1$ 和 $P_2$ 的公共子序列，在 $P_2'$ 中也必须是升序的。 动作：求 $P_1$ 和 $P_2$ 的 LCS $\Longrightarrow$ 求 $P_2'$ 的 最长递增子序列 (LIS)。

4. LIS 的 $O(n \log n)$ 优化

维护一个低能量数组 low，low[k] 表示长度为 k 的递增子序列中，末尾数字最小是多少。利用二分查找进行替换。

---

第四部分：逻辑流程图 (Mermaid)

graph TD
    Start("开始 (C++14)") --> ReadN("输入序列长度 n")
    ReadN --> ReadP1("循环输入 P1: 使用 map 记录每个数字的位置")
    ReadP1 --> ReadP2("循环输入 P2: 按照 map 将值转换为位置序号")
    
    subgraph LIS_Logic ["LIS 优化计算 (O_n_log_n)"]
        InitLow("初始化 low 数组: low_1 = P2_1, len = 1")
        Iterate("遍历 P2 的剩余元素 x")
        Check{"x 大于 low 数组末尾元素?"}
        Push("直接放入末尾: len++")
        BinarySearch("二分查找第一个大于等于 x 的位置并替换")
    end

    ReadP2 --> InitLow
    InitLow --> Iterate
    Iterate --> Check
    Check -- "是" --> Push
    Check -- "否" --> BinarySearch
    
    Push --> Next("所有元素遍历完?")
    BinarySearch --> Next
    Next -- "否" --> Iterate
    Next -- "是" --> Output("输出最终长度 len")
    
    Output --> End("结束")

---

第五部分：复杂度分析与优化建议

1. 时间复杂度思考：
   • 建立映射：$O(n)$。
   • LIS 遍历：$O(n)$。
   • 二分查找：每一次替换操作为 $O(\log n)$。
   • 总计：$O(n \log n)$。在 $1.0\text{s}$ 内处理 $10^5$ 数据非常充裕。
2. 空间复杂度思考：
   • 只需要存储 $P_1$ 的映射表、转换后的 $P_2$ 和 $low$ 数组。
   • 总计：$O(n)$。约 $3 \times 10^5 \times 4 \text{ bytes} \approx 1.2 \text{ MB}$。
3. 时间优化建议：
   • 使用 std::lower_bound 实现 $O(\log n)$ 的二分查找。
   • 使用 scanf 或 cin.tie(0) 加速大数据的读入。

---

第六部分：读题关键词与题意理解

在 NOI 竞赛中，遇到 LCS 题目要重点圈出这些词：

1. “$1, 2, \ldots, n$ 的排列”：
   • 警示：这是本题的灵魂。看到“排列”二字，第一反应是元素唯一性，第二反应就是映射转化。如果不是排列（即元素有重复），则无法使用此 $O(n \log n)$ 优化，必须退回 $O(n^2)$ 或使用复杂的位运算优化。
2. “子序列 (Subsequence)”：
   • 区分：子序列不连续，子串连续。
3. 数据范围 $n \le 10^5$：
   • 强制要求：看到 $10^5$，立刻否定任何 $O(n^2)$ 的 DP，必须寻找 $O(n \log n)$ 或 $O(n)$ 的解法。

教练点评：你之前对 dp[i-1][j-1] 的理解偏差，本质上是对“状态如何通过匹配消耗字符”理解不深。这道题虽然最后转化为了 LIS，但它要求你深刻理解为什么匹配操作对应了序列的顺序性。请在草稿纸上手动模拟那个 $P_2'$ 的转化过程！加油！

---

参考：

播客讲解(Variant 2: Longest Common Substring)