问题1：给出两个长度为 n 的整数序列，求它们的最长公共子序列（LCS）的长度，保证第一个序列中所有元素都不重复；(n<=1e6.m <= 1e6)
设第一个序列为A，第二个序列为B，本题中由于A序列中元素各不相同，我们可以将B序列中所有在A中出现的元素替换为该元素在A序列中的下标，假设替换后的序列为B’，B’的最长公共子序列即为原问题中的最长公共子序列
时间复杂度(n*logn)
题目链接：https://www.acwing.com/problem/content/3513/

#include<bits/stdc++.h> 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
using namespace std;

const int INF = 0x3f3f3f3f;
const int N = 1e6+5;
int n,m,k;
int a[N],b[N];
int p[N];
int ans;
int pos[N];
void solve(int a[],int n){
    int len = 0;
    p[0] = -2*INF;
    for(int i = 1 ; i <= n ; ++i ){
        int l = 0 ,r = len;
        while(l < r){
            int mid = l + r + 1 >> 1;
            if(p[mid] < a[i]) l = mid;
            else r = mid - 1;
        }
        len = max(len,r + 1);
        p[r + 1] = a[i];
    }
    cout << len << endl;
}

int main(){
    IOS;
    cin >> n;
    for(int i = 1 ; i <= n ; ++i) cin >> a[i],pos[a[i]] = i;
    int cnt = 0;
    for(int i = 1 ; i <= n ; ++i){
        cin >> b[i];
        if(pos[b[i]]) a[++cnt] = pos[b[i]];
    }
    solve(a,cnt);
}

问题2：给定两个长度分别为n,m且仅由小写字母构成的字符串A,B ,求A,B 的最长公共子序列。(n <= 1e6,m <= 1e3)

#include<bits/stdc++.h> 
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
#define endl "\n"
using namespace std;

const int INF = 0x3f3f3f3f;
const int N = 1e6 + 5,M = 3005;
int n,m;
char a[N],b[M];
int nxt[N][26];
int f[M][M];
void solve(){
    cin >> n >> a + 1 >> m >> b + 1;
    //预处理每个位置下一个字母的位置 
    for(int i = 0 ; i < 26 ; ++i){
        int cur = INF;
        for(int j = n ; j >= 0 ; --j){
            int t = a[j] - 'a';
            nxt[j][i] = cur;
            if(t == i) cur = j;
        }
    }
    memset(f,0x3f,sizeof(f));
    for(int i = 0 ; i <= m ; ++i) f[i][0] = 0;
    for(int i = 1 ; i <= m ; ++i){
        int t = b[i] - 'a';
        for(int j = 1 ; j <= i ; ++j){
            //不选b[i] 
            f[i][j] = f[i - 1][j];
            //选择b[i],与从前i-1个字母中选，已经匹配了j-1个的位置下一个和b[i]相同的字母的最靠前的位置更新 
            if(f[i - 1][j - 1] <= n) f[i][j] = min(f[i][j],nxt[f[i - 1][j - 1]][t]);
        }
    }
    int ans = 0;
    for(int i = 1 ; i <= m ; ++i){
        if(f[m][i] >= INF) break;
        ans = i;
    }
    cout << ans << endl;
}

signed main(){
    IOS;
    solve();
    return 0;
}