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

Link

Solution:

Get the posistions of numbers of P2 in P1, find the LIS in this position array. 

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

const int maxn=100000+10;
int n;

int a[maxn];
int b[maxn];
int mp[maxn];
int c[maxn];
int f[maxn];
int len;

int main(){
    scanf("%d", &n);
    for(int i=1;i<=n;++i){
        scanf("%d", a+i);
        mp[a[i]]=i;
    }
    for(int i=1;i<=n;++i){
        scanf("%d", b+i);
        c[i]=mp[b[i]];
    }
    for(int i=1;i<=n;++i){
        if(c[i]>f[len]){
            len++;
            f[len]=c[i];
        }else{
            int left=1;
            int right=len;
            while(left<=right){
                int mid=(left+right)>>1;
                if(f[mid]>=c[i]){
                    right=mid-1;
                }else{
                    left=mid+1;
                }
            }
            f[left]=c[i];
        }
    }
    printf("%d", len);
    return 0;
}