文字教学

这道题利用排列的唯一性将LCS（最长公共子序列）转化为LIS（最长递增子序列），再用O(n log n)的算法解决：

1. 映射位置：先记录第一个排列中每个数的位置 pos[x]（x在第一个排列中的下标）。
2. 转化数组：将第二个排列中的每个数替换为它在第一个排列中的位置，得到新数组 b。此时两个排列的LCS等价于 b 的LIS（递增保证顺序在两个排列中都一致）。
3. 求LIS：维护数组 f，f[i] 表示长度为i+1的LIS的最小末尾元素。遍历 b 时，若当前数比 f 末尾大则直接加入，否则用二分找第一个大于等于它的位置替换，最终 f 的长度就是答案。

代码

#include <bits/stdc++.h>
using namespace std;

const int N = 1e5 + 10;
int a[N], p[N], b[N], f[N];

int main() {
    int n, i, x, len, l, r, mid;
    cin >> n;
    for (i = 0; i < n; ++i) {
        cin >> a[i];
        p[a[i]] = i;
    }
    for (i = 0; i < n; ++i) {
        cin >> x;
        b[i] = p[x];
    }
    len = 0;
    for (i = 0; i < n; ++i) {
        x = b[i];
        if (len == 0 || x > f[len - 1]) {
            f[len++] = x;
        } else {
            l = 0;
            r = len;
            while (l < r) {
                mid = (l + r) / 2;
                if (f[mid] >= x) r = mid;
                else l = mid + 1;
            }
            f[l] = x;
        }
    }
    cout << len << endl;
    return 0;
}