题目：P1439 【模板】最长公共子序列 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

关于LCS问题，可以通过离散化转换为LIS问题，于是就可以使用STL二分的方法O(nlogn)解决LCS问题！

先将a数组与一个递增的数列1，2，3...n两两对应（t数组），再把b数组中每个数在a数组中的位置表示成c数组，

经过此番操作，a与b的公共子序列在c数组中就是呈递增状态的。

代码：

#include <iostream>

#include <algorithm>

using namespace std;

typedef long long ll;

const int N = 1e5 + 10;

int a[N], b[N], c[N], r[N], t[N];

int main()

{

    ios::sync_with_stdio(false);

    cin.tie(0);

    cout.tie(0);

    int n;

    cin >> n;

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

    {

        cin >> a[i];

        t[a[i]] = i;//a数组与递增数列1，2，3...n对应

    }

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

        cin >> b[i];

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

    {

        c[i] = t[b[i]];//将b数组中每个元素在a数组中的位置写入c数组

    }

    int cnt = 0;

    for (int i = 1; i <= n; ++i)//使用求解LIS问题的STL二分方法

    {

        if (c[i] > r[cnt])

            r[++cnt] = c[i];

        else

        {

            int pos = lower_bound(r + 1, r + 1 + cnt, c[i]) - r;

            r[pos] = c[i];

        }

    }

    cout << cnt << endl;

    return 0;

}