题解：P1439 【模板】最长公共子序列

#include<bits/stdc++.h>//万能头文件
#define int long long//define:将int替换成long long
using namespace std;
const int N=100100;//数组长度
int a[N],b[N],c[N],dp[N];
int n,i; 
signed main(){//还原（main函数返回值只能为int类型）
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);//快读快写
	cin>>n;
	for(i=1;i<=n;i++){
	    cin>>a[i];
		c[a[i]]=i;//求出a数组的每个数的位置	
	}
	for(i=1;i<=n;i++) cin>>b[i];
	//求b数组的每个数在a数组的位置的LIS
	dp[1]=c[b[1]];//边界 
	//从第二个数开始讨论
	int len=1;
	int l,r,mid;
	for(i=2;i<=n;i++){
		//增加LIS的长度 
		if(c[b[i]]>dp[len]){
			len++;
			dp[len]=c[b[i]];
		}else{
			l=1;r=len;
			while(l<=r){
				mid=l+r>>1;
				if(c[b[i]]<=dp[mid]) r=mid-1;
				else l=mid+1;
			}
			dp[l]=c[b[i]];
		}
	} 
	cout<<len;
	return 0;//圆满结束！！！
}