30分求助

P1439 【模板】最长公共子序列

____X____ @ 2024-07-19 09:23:14

#include<bits/stdc++.h>
using namespace std;
int n,a[100001],b[100001],f[100001],m,l,r,d;
int main(){
    scanf("%d",&n);
    for(int i=1;i<=n;i++){
        scanf("%d",&l);
        a[l]=i;
    }
    for(int i=1;i<=n;i++){
        scanf("%d",&l);
        b[i]=a[l];
    }
    for(int i=1;i<=n;i++){
        l=0,r=m;
        while(l<r){
            d=((l+r)>>1)+1;
            if(f[d]>=b[i])r=d-1;
            else l=d;
        }
        l++;
        r=max(r,l);
        f[l]=(!f[l]?b[i]:min(f[l],b[i]));
        m=max(m,l);
    }
    printf("%d",r);
    return 0;
}

|