题目描述
给出1-n的两个排列P1和P2，求它们的最长公共子序列。

输入格式
第一行是一个数n，

接下来两行，每行为n个数，为自然数1-n的一个排列。

输出格式
一个数，即最长公共子序列的长度

输入输出样例
输入 #1复制
5
3 2 1 4 5
1 2 3 4 5
输出 #1复制
3
说明/提示
【数据规模】

对于50%的数据，n≤1000

对于100%的数据，n≤100000

比较明显，我们需要一个nlogn的做法。

我们想一下，是不是我们把数字等价替换之后，原来的LCS不会改变，这个很明显。

那不是我们把原序列等价替换为 1,2,3,4,5…之后，不就变成求LIS了吗？

直接手速一波。

AC代码：

#pragma GCC optimize(2)
#include<bits/stdc++.h>
//#define int long long
using namespace std;
const int N=1e5+10;
int n,a[N],b[N],cnt;
signed main(){
	cin>>n;
	for(int i=1,x;i<=n;i++)	cin>>x,a[x]=i;
	for(int i=1;i<=n;i++)	cin>>b[i],b[i]=a[b[i]];
	for(int i=1;i<=n;i++){
		if(b[i]>a[cnt])	a[++cnt]=b[i];
		else	a[upper_bound(a+1,a+1+cnt,b[i])-a]=b[i];
	}
	cout<<cnt<<endl;
	return 0;
}