交大的机试还是猛啊！

题目描述

给出两个长度为 n 的整数序列，求它们的最长公共子序列（LCS）的长度，保证第一个序列中所有元素都不重复。

注意：

第一个序列中的所有元素均不重复。
第二个序列中可能有重复元素。
一个序列中的某些元素可能不在另一个序列中出现。

输入格式

第一行包含一个整数 n。

接下来两行，每行包含 n 个整数，表示一个整数序列。

输出格式

输出一个整数，表示最长公共子序列的长度。

数据范围

1≤n≤10^6,
序列内元素取值范围 [1,10^6]。

输入样例1：

5
1 2 3 4 5
1 2 3 4 5

输出样例1：

5

输入样例2：

5
1 2 3 5 4
1 2 3 4 5

输出样例2：

4

题解

这道题目打眼一看是要解决最长公共子序列问题，但是我们仔细一瞧会发现题目的数据范围在[1,10^6]，做场公共子序列需要O(n^2)的时间复杂度，显然这是无法满足要求的，那么怎么办呢？
题目中的注意是一个关键点。

第一个序列中的所有元素均不重复。
第二个序列中可能有重复元素。
一个序列中的某些元素可能不在另一个序列中出现。

当一个最长公共子序列问题中，其中一个子序列满足所有元素均不重复时，那么最长公共子序列问题可以转化成最长上升子序列问题。
证明如下：假设数组A表示第一个序列，且A中不存在重复元素，数组B表示第二个子序列，那么我们可以另开一个数组C表示B中元素在A中的对应位置，那么我们可以惊奇的发现，每一个数组A和数组B的公共子序列都会在数组C中对应一个上升序列，那么我们要求的数组A和数组B的最长公共子序列就对应于数组C中的最长上升子序列。
最长上升子序列的求解有两种方法。DP的方式是O(n^2)的复杂度，贪心的做法是O(nlogn)的复杂度。这里由于数据范围较大，因此应该选用贪心的做法。

求最长上升子序列贪心做法

这个序列是单调递增的证明如下，利用反证法证明。

那么，有上面的结论就有了一个特别好的性质。我们此时进来一个值x，那么这个x只需要更新最小末尾值刚好大于x的第一个上升子序列。为什么呢？除最小末尾值刚好大于x的第一个序列可以用前一个位置加上x更新外，不能更新。小于x的值，也无法被更新，如下图所述。

这样的话，我们就可以每次利用二分来找到可以更新的位置，然后边找边更新答案。
时间复杂度为O(nlogn)

代码

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1000010;

int n;
int id[N], q[N];

int main()
{
    scanf("%d", &n);
    memset(id, -1, sizeof id);
    for (int i = 0; i < n; i ++ )
    {
        int x;
        scanf("%d", &x);
        id[x] = i;
    }

    int tt = 0;
    q[0] = -1;
    for (int i = 0; i < n; i ++ )
    {
        int x;
        scanf("%d", &x);
        int k = id[x];
        if (k == -1) continue;
        int l = 0, r = tt;
        while (l < r)
        {
            int mid = l + r + 1 >> 1;
            if (q[mid] < k) l = mid;
            else r = mid - 1;
        }
        q[r + 1] = k;
        tt = max(tt, r + 1);
    }

    printf("%d\n", tt);
    return 0;
}