See LCS again

时间限制：

1000 ms  |  内存限制：

65535 KB

难度：

3

描述

There are A, B two sequences, the number of elements in the sequence is n、m;

Each element in the sequence are different and less than 100000.

Calculate the length of the longest common subsequence of A and B.

输入

The input has multicases.Each test case consists of three lines;

The first line consist two integers n, m (1 < = n, m < = 100000);

The second line with n integers, expressed sequence A;

The third line with m integers, expressed sequence B;

输出

For each set of test cases, output the length of the longest common subsequence of A and B, in a single line.

样例输入

5 41 2 6 5 41 3 5 4

样例输出

3

上传者

    东哥的题，，TC元老级人物，请收下15级菜鸡的膝盖。

   很裸的求LCS。但基于数据大，所以超时的做法不用考虑了。看提交纪律很多MLE的，于是用滚动数组。。WA了。于是在网上找了一种很暴力钻数据空子的做法。详见：

  其实这种做法以前寒假学LCS的时候在网上看到过，当时和小田说了一下，我们都很震惊。但后来被他所举的例子也就是上面博客中提到的例子退化的LCS所推翻了。基于数据水的前提下是可以试试的。一下摘自上面那位大神的博客：

这里也可将其转化为最长递增子序列问题。

举例说明：

A：abdba

B：dbaaba

则1：先顺序扫描A串，取其在B串的所有位置：

    2：a(2,3,5) b(1,4) d(0)。

    3：用每个字母的反序列替换，则最终的最长严格递增子序列的长度即为解。

替换结果：532 41 0 41 532

最大长度为3.

简单说明：上面的序列和最长公共子串是等价的。

对于一个满足最长严格递增子序列的序列，该序列必对应一个匹配的子串。

反序是为了在递增子串中，每个字母对应的序列最多只有一个被选出。

反证法可知不存在更大的公共子串，因为如果存在，则求得的最长递增子序列不是最长的，矛盾。

最长递增子序列可在O(NLogN)的时间内算出。

  配上代码：

const int N=1e5+7;int c[N],d[N],a[N],b[N],v[N];int find(int x,int *a,int len){  int l=0,r=len;  while(l<=r)  {      int mid=(l+r)/2;      if(a[mid]==x) return mid;      if(a[mid]