AcWing夏季每日一题--最长公共子序列

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 1e6+10;
int q[N],id[N];
int main()
{
    int n;
    cin>>n;
    memset(id,-1,sizeof id);
    for(int i=1;i<=n;i++){
        int x;
        scanf("%d",&x);
        id[x]=i;
    }
    int tt=0;
    q[0]=-1;
    for(int i=1;i<=n;i++){
        int x;
        scanf("%d",&x);
        int k=id[x];
        if(k==-1) continue;
        int l=0,r=tt;
        while(l<r){//找到小于k的最大的
            int mid=l+r+1>>1;
            if(q[mid]>=k) r=mid-1;
            else l=mid;
        }
        q[r+1]=k;
        tt=max(tt,r+1);
    }
    cout<<tt<<endl;
    return 0;
}