链接：https://www.luogu.org/problemnew/show/P1439
$Time\;Limit:\;1000\;ms$
$Memory\;Limit:\;128\;MB$
给出$1-n$的两个排列$P1$和$P2$，求它们的最长公共子序列。
第一行是一个数$n$，
接下来两行，每行为$n$个数，为自然数$1-n$的一个排列。
一个数，即最长公共子序列的长度
5
3 2 1 4 5
1 2 3 4 5
3
【数据规模】
对于$50\%$的数据，$n\le 1000$
对于$100\%$的数据，$n\le100000$
将$P1$中的数换成$1-n$，用数组记录下对应的替换
然后将$P2$中的数依$P1$的数字对应关系变换
易知变换后$P2$各位的值即其在$P1$中的位置
那么题目变成了求$P2$最大上升子序列长度的问题
拿个$O(nlog_2n)$的板子套一下即可
//Time: 147ms Memory: 1692KB
#include <bits/stdc++.h>
using namespace std;
int P2[100005], b[100005], d[100005];
int main()
{
ios::sync_with_stdio(0);
int n, temp;
cin >> n;
for(int i = 1; i <= n; ++i)
{
cin >> temp;
b[temp] = i;
}
for(int i = 1; i <= n; ++i)
{
cin >> temp;
P2[i] = b[temp];
}
d[1] = P2[1];
int len = 1;
for(int i = 2; i <= n; ++i)
{
if(P2[i] > d[len])
d[++len] = P2[i];
else
{
int j = lower_bound(d + 1, d + len + 1, P2[i]) - d;
d[j] = P2[i];
}
}
cout << len << endl;
}