BZOJ 1264 AHOI 2006遺伝子マッチングMatchダイナミックプランニング+ツリー配列


n個の数と2個の長さのn*5の序列を与えて、それぞれの数はちょうど5回現れて、2個の序列のLCSを求めます
n<=20000、シーケンス長は10 W、地味なO(n^2)は必ずタイムアウト
LCSのいくつかの性質を考えてみましょう
LCSの決定+1の条件はa[i]=b[j]であり,aシーケンスの各数の5つの位置を記録した.
b[i]をスキャンすると、b[i]毎にb[i]がa中の5つの位置を見つけるという5つの位置の各f[pos]値がb[i]毎に更新できるので、f[1]からf[pos-1]までの最大値+1を見つけてf[pos]を更新すればよい
このツリー配列によるメンテナンス時間の複雑さO(nlogn)
難しい問題ですが、難しくはありません.
#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
#define M 200200
using namespace std;
int n,ans,a[M*5],b[M*5],c[M*5],f[M*5],pos[M][6];
void Update(int x,int y)
{
	for(;x<=n*5;x+=x&-x)
		c[x]=max(c[x],y);
}
int Get_Ans(int x)
{
	int re=0;
	for(;x;x-=x&-x)
		re=max(re,c[x]);
	return re;
}
int main()
{
	int i,j;
	cin>>n;
	for(i=1;i<=n*5;i++)
	{
		scanf("%d",&a[i]);
		pos[ a[i] ][ ++pos[a[i]][0] ]=i;
	}
	for(i=1;i<=n*5;i++)
		scanf("%d",&b[i]);
	for(i=1;i<=n*5;i++)
	{
		for(j=5;j;j--)
		{
			int k=pos[b[i]][j];
			f[k]=max( f[k] , Get_Ans(k-1)+1 );
			Update(k,f[k]);
			ans=max(ans,f[k]);
		}
	}
	cout<<ans<<endl;
}