1822: 【提高】最长公共子序列(LCS)(2)
内存限制：128 MB
时间限制：1.000 S
评测方式：文本比较
命题人：
提交：9
解决：4
题目描述
给出1-n的两个排列P1和P2，求它们的最长公共子序列。
和最长公共子序列(LCS)(1)问题不同的是，本题的n在5-100000之间。
和最长公共子序列(LCS)(1)问题不同的是，本题的n在5-100000之间。
输入
第一行是一个数n；（n是5-100000之间的整数）
接下来两行，每行为n个数，为自然数1-n的一个排列（1-n的排列每行的数据都是1-n之间的数，但顺序可能不同，比如1-5的排列可以是：1 2 3 4 5，也可以是2 5 4 3 1）。
接下来两行，每行为n个数，为自然数1-n的一个排列（1-n的排列每行的数据都是1-n之间的数，但顺序可能不同，比如1-5的排列可以是：1 2 3 4 5，也可以是2 5 4 3 1）。
输出
一个整数，即最长公共子序列的长度。
样例输入 复制
5
3 2 1 4 5
1 2 3 4 5样例输出 复制
3提示
对于50%的数据，n≤1000
对于100%的数据，n≤100000
对于100%的数据，n≤100000