analysis

LCS是Longest Common Subsequence的缩写，即最长公共子序列。一个序列，如果是两个或多个已知序列的子序列，且是所有子序列中最长的，则为最长公共子序列。
比如，对于char x[]=“aabcd”;有顺序且相互相邻的aabc是其子序列，有顺序但是不相邻的abc也是其公共子序列。即，只要得出序列中各个元素属于所给出的数列，就是子序列。
再加上char y[]=“12abcabcd”;对比出才可以得出最长公共子序列abcd。

对于本题来说好像有比较凑巧的求解方法，即将P1离散化为单调增，然后将P2按相同的规则离散，最后对P2求一边LIS即可

最长上升子序列（Longest Increasing Subsequence，LIS），在计算机科学上是指一个序列中最长的单调递增的子序列。

至于为什么可以离散然后操作，这有比较详尽的解释

现在问题就转化为如何求LIS

首先O（${n}^{2}$n2）的一般求法肯定拿不满分，60pts是运气好
这里有一种nlogn的算法，其实质上是来源于n方的暴力，不过利用了二分的思想将n优化到了logn
附上几篇blog，感觉自己讲不清楚
其一.
其二.

code

#include<bits/stdc++.h>
using namespace std;
#define loop(i,start,end) for(register int i=start;i<=end;++i)
#define anti_loop(i,start,end) for(register int i=start;i>=end;--i)
#define max(a,b) ((a>b)?a:b)
#define min(a,b) ((a<b)?a:b)
#define clean(arry,num) memset(arry,num,sizeof(arry))
#define ll long long
const int maxn=100000+10;
int a[maxn];
int b[maxn];
int c[maxn];
int n;
int f[maxn];
template <typename T> void read(T &x)
{
    x=0;char r=getchar();T neg=1;
    while(r>'9'||r<'0'){if(r=='-')neg=-1;r=getchar();}
    while(r>='0'&&r<='9'){x=(x<<3)+(x<<1)+r-'0';r=getchar();}
    x*=neg;
}
inline void datasetting()
{
    read(n);
    loop(i,1,n)read(a[i]);
    loop(i,1,n)read(b[i]);
    loop(i,1,n)c[a[i]]=i;
    loop(i,1,n)b[i]=c[b[i]];
}
int main()
{
    #ifndef ONLINE_JUDGE
    freopen("datain.txt","r",stdin);
    #endif
    datasetting();
    clean(f,0);
    int res=0;
    loop(i,1,n)
    {
    	if(i<=1||f[res]<b[i])
    	{
    		f[res+1]=b[i];
            ++res;
        }
        else 
        {
            f[lower_bound(f+1,f+res+1,b[i])-f]=b[i];
        }
    }
    printf("%d",res);
    return 0;
}