可以发现只有当两个序列中都没有重复元素时（1～n的排列）此种优化才是高效的，不然可能很不稳定。

求a[] 与b[]中的LCS

通过记录lis[i]表示a[i]在b[]中的位置，将LCS问题转化为最长上升子序列问题，转化方法如下：

for(int i=1;i<=n;i++){        local[b[i]]=i;    }    for(int i=1;i<=n;i++){        lis[i]=local[a[i]];    }

当序列中有元素重复时，我们们需要保证对于每个a[i]所记录的位置必须是逆序的，以保证一个元素只取一次。

例：举例说明：

A：abdba

B：dbaaba

则1：先顺序扫描A串，取其在B串的所有位置：

2：a(2,3,5) b(1,4) d(0)。

3：用每个字母的反序列替换，则最终的最长严格递增子序列的长度即为解。

替换结果：532 41 0 41 532

代码如下：

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;int read(){    int rv=0,fh=1;    char c=getchar();    while(c<'0'||c>'9'){        if(c=='-') fh=-1;        c=getchar();    }    while(c>='0'&&c<='9'){        rv=(rv<<1)+(rv<<3)+c-'0';        c=getchar();    }    return fh*rv;}int n,a[100005],b[100005],local[100005],lis[100005],dp[100005];int main(){    freopen("in.txt","r",stdin);    n=read();    for(int i=1;i<=n;i++){        a[i]=read();    }    for(int i=1;i<=n;i++){        b[i]=read();    }    for(int i=1;i<=n;i++){        local[b[i]]=i;    }    for(int i=1;i<=n;i++){        lis[i]=local[a[i]];    }    dp[1]=lis[1];dp[0]++;    for(int i=2;i<=n;i++){        int l=1,r=dp[0],m=0;        while(l<=r){            m=(l+r)>>1;            if(dp[m]<=lis[i]){                l=m+1;            }else r=m-1;        }        if(l==1){            dp[l]=min(dp[l],lis[i]);        }else {            if(l==dp[0]+1){                dp[0]++;                dp[l]=lis[i];            }else {                dp[l]=min(dp[l],lis[i]);            }        }    }    cout<