bzoj 1264: [AHOI2006]基因匹配Match

.

题意：求两个5n长的序列的最长公共子序列
题解：$O(nlogn)$的最长公共子序列。
一般的最长公共子序列是$O(n^2)$的，但对于这道题完全过不去。$O(nlogn)$的做法就是把最长公共子序列转化为求最长上升子序列。我们可以求出s2中的每个数对应的s1中数的位置，把它们按照s2里的顺序排好，那么这个新的数列的最长上升子序列就是最长公共子序列。例如样例：
1 1 2 2 1 1 2 1 2 2
1 2 2 2 1 1 2 2 1 1
1对应着位置1,2,5,6,8，2对应着3,4,7,9,10。把它们从大到小排序（防止一个s2对应多个s1），然后按s2的顺序排好。就像这样：
8,6,5,2,1, 10,9,7,4,3, 10,9,7,4,3, 10,9,7,4,3, 8,6,5,2,1…
然后就可以用$O(nlogn)$的时间求出来了。但不是严格$O(nlogn)$，因为假如一个数对应了很多个数，最后的数列就会变得很长，最差会退化成$O(n^2)$。
代码：

#include<cstdio>
#include<cstring>
#include<vector>
#include<algorithm>
#include<iostream>
using namespace std;

int n;
vector<int>a,pos[1000010];

int main()
{
    scanf("%d",&n);
    int nn=n*5;
    for(int i=1;i<=nn;i++)
    {
        int x;
        scanf("%d",&x);
        pos[x].push_back(i);
    }
    for(int i=1;i<=n;i++)
    sort(pos[i].begin(),pos[i].end(),greater<int>());
    for(int i=1;i<=nn;i++)
    {
        int x;
        scanf("%d",&x);
        a.insert(a.end(),pos[x].begin(),pos[x].end());
    }
    vector<int>s;
    int sz=a.size();
    for(int i=0;i<sz;i++)
    {
        vector<int>::iterator it=lower_bound(s.begin(),s.end(),a[i]);
        if(it==s.end())
        s.push_back(a[i]);
        else
        *it=a[i];
    }
    printf("%d",s.size());
}