bzoj1264

表面上看这是一道LCS问题

LCS问题O(n2)的复杂度已经很优秀了

而这道题需要O(nlogn)以下的复杂度才能AC

所以我们要找经典问题的特殊性

特殊就在这两个串中，每个数字都是恰好出现5次

不难想到先预处理每个数在B串依次出现的位置

先扫一遍A串，对于每一个数a[i]，设f[j]=LCS(i,j)

显然这个数在B串出现的位置才会更新答案

对于每个出现的位置x1~x5,显然f[x]=max(f[w])+1 (1<=w<=x-1);

为了避免重复更新，我们要从后往前更新f[x]

再考虑怎么快速找到最大值，显然这里要找的是前缀中的最大值

不难想到，我们可以通过树状数组维护

var b,f,a,c:array[0..100010] of longint;
    w:array[0..100010,0..5] of longint;
    j,n,i,x,ans:longint;

function max(a,b:longint):longint;
  begin
    if a>b then exit(a) else exit(b);
  end;

function lowbit(x:longint):longint;
  begin
    exit(x and (-x));
  end;

function get(x:longint):longint;
  begin
    get:=0;
    while x>0 do
    begin
      get:=max(get,c[x]);
      x:=x-lowbit(x);
    end;
  end;

procedure update(x,p:longint);
  begin
    while x<=5*n do
    begin
      c[x]:=max(c[x],p);
      x:=x+lowbit(x);
    end;
  end;

begin
  readln(n);
  for i:=1 to 5*n do
    read(a[i]);
  for i:=1 to 5*n do
  begin
    read(x);
    inc(b[x]);
    w[x,b[x]]:=i;
  end;
  for i:=1 to 5*n do
  begin
    for j:=5 downto 1 do
    begin
      x:=w[a[i],j];
      f[x]:=get(x-1)+1;
      update(x,f[x]);
    end;
  end;
  for i:=1 to 5*n do
    ans:=max(f[i],ans);
  writeln(ans);
end.