#include<iostream>
#include<vector>
using namespace std;
int main()
{
int n; cin >> n;
vector<int>p1(n), p2(n);
vector<int>pos(n + 5);
for (int i = 0; i < n; i++)
{
cin >> p1[i];
pos[p1[i]]=i;
}
vector<int>a(n + 5);
for (int i = 0; i < n; i++)
{
cin >> p2[i];
a[i] = pos[p2[i]];
}
vector<int>tail;
for (int i = 0; i < a.size(); i++)
{
int x = a[i];
auto it = lower_bound(tail.begin(), tail.end(), x);
if (it == tail.end())
{
tail.push_back(x);
}
else
{
*it = x;
}
}
cout << tail.size() << endl;
}
P1439 两个排列的最长公共子序列：从LCS到LIS的降维打击
这道题如果你按“普通LCS”去写，大概率会直接超时。因为数据范围 n ≤ 1e5，经典 O(n²) 的动态规划是扛不住的。
但这题的精髓就在于一句话：
排列的LCS问题，可以转化为LIS问题
这篇文章就把这个转化过程讲清楚，顺便把你这份代码彻底拆明白。
问题回顾；看起来是LCS
题目给你两个排列：
P1：1~n 的一个排列
P2：1~n 的一个排列
要求：
它们的最长公共子序列长度
第一反应：
-
LCS模板
-
dp[i][j]
但一看数据范围：
n ≤ 100000
直接宣告：
不能用传统LCS
关键突破；排列的特殊性质
注意这句话：
两个序列都是 1~n 的排列
这意味着：
-
没有重复元素
-
每个数只出现一次
这就是突破口。
核心思路；把值变成位置
我们先处理 P1：
pos[p1[i]] = i;
意思是：
每个数在 P1 中的位置
例如：
P1: 3 2 1 4 5
pos[3]=0
pos[2]=1
pos[1]=2
pos[4]=3
pos[5]=4
然后处理 P2；做映射
a[i] = pos[p2[i]];
什么意思？
把 P2 中的“值”，转换成它在 P1 中的“位置”
例如：
P2: 1 2 3 4 5
→ a: 2 1 0 3 4
关键转化；问题变了
现在问题变成：
在数组 a 中，求最长上升子序列（LIS）
为什么？
因为：
-
公共子序列 → 相对顺序一致
-
转成位置后 → 就是“递增”
一句话总结：
LCS → 转化为 LIS（在排列问题中成立）
LIS怎么做；用二分优化
你用的是经典的 O(n log n) 做法：
vector<int> tail;
含义：
tail[i] 表示长度为 i+1 的上升子序列的最小结尾
核心代码解释
auto it = lower_bound(tail.begin(), tail.end(), x);
这一步是关键：
; 找到第一个 >= x 的位置
; 如果没有 → 直接加到末尾
; 如果有 → 替换
为什么可以替换
这是很多人最困惑的地方。
举个例子：
tail = [1, 3, 5]
来了个 x = 2：
替换后 → [1, 2, 5]
虽然看起来“变小了”，但：
更小的结尾 → 更有潜力变长
整体流程串起来
你的代码本质做了三件事：
; 建立位置映射
pos[x] = 在P1中的位置
; 转换数组
a[i] = pos[P2[i]]
; 求LIS
lower_bound + 贪心
时间复杂度分析
-
映射：O(n)
-
LIS：O(n log n)
总复杂度：
O(n log n)
完全能通过 1e5 数据。
为什么一定要用 lower_bound
这里必须用：
lower_bound（>=）
不能用 upper_bound（>）
原因是：
我们要保证“严格递增”
常见误区
; 还在用二维dp做LCS
直接超时
; 不理解为什么能转LIS
核心是“排列无重复”
; lower_bound用错
会导致结果错误
总结一句话
这题最关键的不是代码，而是这个转化：
排列的LCS → 转换为位置序列 → 求LIS
最后
如果你能掌握这道题，其实你已经掌握了一个非常重要的套路：
降维打击：把二维问题变成一维问题
这在算法里是非常核心的一种能力，比单纯会写代码重要得多。
