题意描述：有两个长度分别为p+1和q+1的序列，每个元素中的各个元素互不相同。都是1~n^2之间的整数，求A和B的最长公共子序列。（2<=n<=250，1<=p,q<=n^2）
分析：本题是LCS问题，但因为p和q可以高达250^2=62500，O(pq)的算法显然太慢。注意到A序列中所有元素互不相同，因此可以把A中的元素重新编号为1~p+1。这样新的A和B的LCS实际上就是B的LIS。可以在O(nlogn)时间内解决。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=*;
const int INF=;
int s[maxn],g[maxn],d[maxn];
int num[maxn]; int main()
{
int T;
scanf("%d",&T);
for(int kase=;kase<=T;kase++)
{
int N,p,q,x;
scanf("%d %d %d",&N,&p,&q);
memset(num,,sizeof(num));
for(int i=;i<=p+;i++) {scanf("%d",&x);num[x]=i;}
int n=;
for(int i=;i<q+;i++) {scanf("%d",&x);if(num[x]) s[n++]=num[x];}
for(int i=;i<=n;i++) g[i]=INF;
int ans=;
for(int i=;i<n;i++)
{
int k=lower_bound(g+,g++n,s[i])-g;
d[i]=k;
g[k]=s[i];
ans=max(ans,d[i]);
}
printf("Case %d: %d\n",kase,ans);
}
return ;
}