[Daimayuan] 最长公共子序列（C++，DP，二分，最长上升子序列）

给出从 $1$ 到 $n$ 的两个排列 P 1 P_1 P1​ 和 P 2 P_2 P2​，求它们的最长公共子序列。

输入格式

第一行是一个正整数 $n$。

接下来两行，每行为 $n$ 个数，为自然数 $1,2,\dots ,n$ 的一个排列。

输出格式

一个数，即最长公共子序列的长度。

数据范围

1 ≤ n ≤ 1 0 5 1≤n≤10^5 1≤n≤105

输入样例

5 
3 2 1 4 5
2 1 3 4 5

输出样例

4

解题思路

根据数据范围，我们需要一个$O(N)$或者$O(NlogN)$的算法，自然会想到动态规划。

与本题相似的题型有最长公共子序列（$LCS$，复杂度 O ( N 2 ) O(N^2) O(N2)），最长上升子序列（复杂度$O(N(N-1)/2$)

表面上看一眼好像最长公共子序列和最长上升子序列并没有什么联系（不是有公共和子序列嘛）

但实际上是有的。我们来重新审视一下最长上升子序列问题：

给定一个序列，我们需要找出一个最长的单调上升的子序列，但实际上我们找出来的并不只是一个序列，而是两个：索引单调递增、值也单调递增。

然后反观本题的题意，可以发现$n$个数对应$1,...,n$的全排列这个条件，这个条件允许我们反转值和索引的关系（与索引和值的关系一致，值和索引也都是一一对应的，并无重复）。

到这里，我们可以实现以下的代码，将本题转换为找出最长上升子序列的问题：

int n, temp;
cin >> n;
for (int i = 0; i < n; i++) {cin >> temp;indices[temp] = i;//a序列值到索引的映射
}
for (int i = 0; i < n; i++) {cin >> temp;arr[i] = indices[temp];//arr[i]为b_i在a序列中的位置
}

但是我们之前说过了，常规的最长上升子序列的算法时间复杂度为$O(N(N-1)/2$，不可接受。

可以优化的地方就是常规动态规划算法中，搜索最长前缀的那部分（这里不再赘述）。

优化搜索的常用方法就是二分搜索，但是要求是问题具有单调性，接下来我们看看这个问题为什么具有单调性：

直接开始模拟我们的算法，通过模拟来理解。

维护一个前缀和数组tails与当前最长上升子序列长度len，起初，len=0, tails[0]=-NaN（-NaN即为负无穷）。

然后与常规算法思路相一致，我们首先搜索以a[0]结尾的最长上升子序列，搜索思路是找到当前有效长度tails数组中，比a[0]大的最小元素。

显然，（1）这个元素并不存在（因为有效长度len=0），所以我们扩增长度len=1。

然后继续尝试搜索以a[1]结尾的最长上升子序列，思路是一致的，但是可能会出现（2）另一种情况——a[1]<a[0]。

当出现这种情况时，我们把$a[1]$用$a[0]$覆盖，因为当上升序列长度相同的时候，我们希望结尾元素尽可能地小。

依次类推，直到所有元素都遍历完成。

接下来给出规范化的思路：

（1）搜索当前tails数组，寻找比a[i]大的元素；

（2）不存在该元素，扩增有效长度len；

（3）存在该元素，覆盖它。

实现代码如下

tails[0] = -NaN;
for (int i = 0; i < n; i++) {int l = 0, r = len + 1, m;while (l + 1 != r) {m = l + r >> 1;if (arr[i] > tails[m]) l = m;else r = m;}tails[r] = arr[i];len = max(len, r);
}

最后，AC代码如下：

#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
const int max_n = 1e5;
const int NaN = 0x3F3F3F3F;int arr[max_n], indices[max_n];
int tails[max_n], len = 0;int main() {int n, temp;cin >> n;for (int i = 0; i < n; i++) {cin >> temp;indices[temp] = i;}for (int i = 0; i < n; i++) {cin >> temp;arr[i] = indices[temp];}tails[0] = -NaN;for (int i = 0; i < n; i++) {int l = 0, r = len + 1, m;while (l + 1 != r) {m = l + r >> 1;if (arr[i] > tails[m]) l = m;else r = m;}tails[r] = arr[i];len = max(len, r);}printf("%d", len);return 0;
}