洛谷1439：最长公共子序列（nlogn做法）

题目描述：

• 给定两个序列求最长公共子序列。
• 这两个序列一定是\(1\)~\(n\)的全排列。

数据范围:

• \(1\leq n\leq 10^5\)

思路：

• \(n^2\)很好做，不赘述。

• 这里有个很好的一点就是两个序列都一定是全排列，说明两个序列的元素出现的位置不一样而已，但是数字是一样的。

• 通过\(vis\)来记录\(A\)序列的数字出现的位置，自然也可以对应到\(B\)的位置。

• 接下来的步骤看样例解释一下吧。

• 比如说\(A\)串：\(3\ 2\ 1\ 4\ 5\)，对应的位置是\(3-1,2-2,1-3,4-4,5-5\)。

• 那么对于\(B\)串：\(1\ 2\ 3\ 4\ 5\)，对应的位置是\(1-3,2-2,3-1,4-4,5-5\)。

• 也就是\(3\ 2\ 1\ 4\ 5\)，这时候求这个序列的\(LIS\)就行了，\(LIS\)的\(nlogn\)做法已知。

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e5 + 10;

int a[maxn], b[maxn], c[maxn], n;

int f[maxn], vis[maxn], len;

int bin_search(int x)

{

    int l = 1, r = len;

    while(l < r)

    {

        int mid = (l + r) >> 1;

        if(x <= f[mid]) r = mid;

        else l = mid + 1;

    } return l;

}

int main()

{

    scanf("%d", &n);

    for(int i = 1, x; i <= n; i++)

    {

        scanf("%d", &x);

        a[i] = x;

        vis[x] = i;

    }

    for(int i = 1; i <= n; i++)

    {

        scanf("%d", &b[i]);

        c[i] = vis[b[i]];

    }

    len = 1; f[1] = c[1];

    for(int i = 2; i <= n; i++)

    {

        if(c[i] > f[len])

            f[++len] = c[i];

        else

        {

            int pos = bin_search(c[i]);

            f[pos] = c[i];

        }

    }

    cout << len << endl;

    return 0;

}