UVA 10635 Prince and Princess(最長共通サブシーケンス+最長上昇サブシーケンス)

テーマ:
2つの数値シーケンスが与えられ、各シーケンスは繰り返されず、2つのシーケンスの最長共通シーケンスが求められる.
問題を解く:
2つのシーケンスの複雑度をn^2とすると,構造を求めるシーケンスの最長上昇サブシーケンスに変換でき,複雑度をNlog(N)に変換できる.このブログLCS最長共通サブシーケンスを参考にすることができます
コード:

#include <iostream>
#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
using namespace std;
int pos[70000],a[70000],b[70000],arr[70000],val[70000],d[70000],cnt,len;
int binary_search(int i)
{  
    int left,right,mid;  
    left=0,right=len;  
    while(left<right){  
        mid = left+(right-left)/2;  
        if(d[mid]>=arr[i]) right=mid;  
        else left=mid+1;  
    }  
    return left;  
}  
int LIS()  
{  
	d[1] = arr[1];  
	len=1;  
	for(int i=2; i<cnt; ++i)
	{  
		if(arr[i]>d[len])  
			d[++len]=arr[i];  
		else{  
			int p=binary_search(i);   
			d[p] = arr[i];  
		} 
	}  
	return len;
}
int main()
{
    int t,x,m,n;
	scanf("%d",&t);
	for(int i=1;i<=t;i++)
	{
		cnt=1;
		memset(pos,-1,sizeof(pos));
        scanf("%d%d%d",&x,&m,&n);
		for(int j=1;j<=m+1;j++)
			scanf("%d",&a[j]);
		for(int j=1;j<=n+1;j++)
			scanf("%d",&b[j]);

		for(int j=1;j<=n+1;j++)
			pos[b[j]]=j;

        for(int j=1;j<=m+1;j++)
		{
			if(pos[a[j]]!=-1)
				arr[cnt++]=pos[a[j]];
		}
		printf("Case %d: %d
",i,LIS());
	}
}