美团26春招笔试第五场/全栈方向 第三题

气笑了,写了半个小时感觉没GPT讲的好,喂给GPT帮我重写了一下,但是有些缩写没说明
LCS = Longest Common Subsequence，最长公共子序列
LIS = Longest Increasing Subsequence，最长上升子序列
BIT = Binary Indexed Tree，树状数组
suf[i] = suffix 的缩写，这里表示“从 i 开始的最优长度”

给你两个长度为 2e5 的排列 p 和 q，
求它们的最长公共子序列中字典序最大的一个。

例如：
10
4 7 8 9 5 10 2 1 3 6
3 2 6 10 8 9 1 4 5 7

ans: 8 9 5

补了半天，也是补出来了。

整体思路其实分两步：

第一步，先把 LCS 转化成 LIS。
因为 p 和 q 都是排列，
所以每个数在 q 中出现的位置唯一。
把 p 中每个数替换成它在 q 里的下标，
原问题就转化成了求最长上升子序列。

第二步，为了方便构造字典序最大的答案，
记录每个位置的 suf[i]。
suf[i] 的意思是：
如果当前选了第 i 个位置，
并且把它作为这一段的开头，
那么从这里开始最多还能选出多长的合法序列。
注意，这个长度是包含当前位置自己的。

然后贪心构造答案。
从最大的 suf 开始往下做，
每次都在当前这一层里选能选到的最大值。

这里“能选到”不只是原排列里位置要在后面，
还要求它映射到 q 里的位置也在后面。
这两个条件都满足，
才能保证它仍然是公共子序列。

时间复杂度分析：

映射下标 O(n)。

算 suf[i]，
本质上还是 LIS 的 DP，
可以用二分 / 树状数组 BIT 加速到 O(nlogn)。

构造时，
把 suf 相同的位置放到同一个桶里，
同时记录它们的原值和原下标。
每个桶内按值从大到小排序，
然后从大到小枚举 suf，
顺着扫一遍找第一个合法位置即可。

这样排序总复杂度是 O(nlogn)，
最后构造整体扫一遍是 O(n)。

所以总复杂度是 O(nlogn)，
2e5 可以通过。

下面说一下为什么能转成 LIS。

最长公共子序列这题，
如果两个序列都是排列，
那么把其中一个排列里的元素，
替换成它在另一个排列中的下标，
就可以转成 LIS。

核心原因是：

“值相同且顺序一致”
等价于
“映射后的下标严格递增”。

这一步成立的关键条件就是：
排列里的每个数只出现一次。

比如在 p 中选出一个公共子序列：
p[i], p[j], p[k]

如果它在 q 中也按同样顺序出现，
那么它们在 q 里的位置一定满足：

pos[p[i]] < pos[p[j]] < pos[p[k]]

所以公共子序列就对应着一个上升子序列，
LCS 也就变成了 LIS。

最后说一下 BIT 为什么能算 suf。

这个本质上还是 LIS 的 DP。

如果从右往左扫，
设 suf[i] 表示以 i 位置开头时最多能选多少个，
那么转移就是：

suf[i] = 1 + max(suf[j])，其中 j > i 且 p[j] > p[i]

也就是：
要从右边、并且值比当前大的位置里，
找一个最优的接在后面。

这个可以用 BIT 维护前缀 max 来加速。

因为 BIT 的结构天然适合维护前缀信息，
后面的块会汇总前面的信息，
而前面的不会被后面的影响。
只要维护的是 max 这种可合并的信息，
就能像维护前缀和一样维护前缀最大值。

而这里值域又正好是 1..n 的排列，
所以非常适合直接用 BIT 做到 O(nlogn)。

#美团笔试##牛客AI配图神器#