3 Dバイアスツリー&cdq分治

一般的な最長上昇サブシーケンスは2次元バイアスなので、ソート後にセグメントツリーでメンテナンスするとnlogn程度になりますが、3元グループなら?
オフセット関係が1つ増えたので、メンテナンスがかなり面倒です.
roosephuは古典的なことを言いました:1次元の速い列、2次元の集計、3次元の木の配列、1次元のソートxの後で、更に速い列で前の1段のxが後の1段のxより小さいことを保証した上でyを集計して、同時にこの基礎の上で木の配列はzを維持します.(詳しくはhttp://blog.csdn.net/cjoilmd/article/details/6884432ああ、スピードオーバーstd)
しかし、ツリーカバーを使うとそれほど面倒ではありません.1次元ソート後、2、3次元セグメントツリーカバーバランスツリーです.
事実はroosephuが丹念にランダムなデータの下で裸bstがtreapより半分以上速いことを証明した.
(隠れているのはtreap回転などの操作)

{$inline on}
uses math;
type rex=record
      x,y,z:longint
     end;
var rt,l,r,d,id,key,maxk:array[1..1048576]of longint;
    ans,ss,n,m,m1:longint;
    f:array[1..500000]of longint;
    a:array[1..500000]of rex;
procedure inf;
begin
 assign(input,'godfarmer.in');reset(input);
 assign(output,'godfarmer.out');rewrite(output)
end;
procedure ouf;
begin
 close(input);close(output)
end;
{procedure left(x:longint);inline;
var y,z:longint;
begin
 y:=rt[x];z:=rt[y];
 if l[z]=y then l[z]:=x else r[z]:=x;rt[x]:=z;
 r[y]:=l[x];rt[l[x]]:=y;
 l[x]:=y;rt[y]:=x;
 maxk[y]:=max(maxk[l[y]],max(maxk[r[y]],key[y]));
 maxk[x]:=max(maxk[l[x]],max(maxk[r[x]],key[x]));
 maxk[z]:=max(maxk[l[z]],max(maxk[r[z]],key[z]))
end;
procedure right(x:longint);inline;
var y,z:longint;
begin
 y:=rt[x];z:=rt[y];
 if l[z]=y then l[z]:=x else r[z]:=x;rt[x]:=z;
 l[y]:=r[x];rt[r[x]]:=y;
 r[x]:=y;rt[y]:=x;
 maxk[y]:=max(maxk[l[y]],max(maxk[r[y]],key[y]));
 maxk[x]:=max(maxk[l[x]],max(maxk[r[x]],key[x]));
 maxk[z]:=max(maxk[l[z]],max(maxk[r[z]],key[z]))
end;}
function ori(i,x,w:longint ): longint;inline;
begin
 inc(ss);rt[ss]:=i;d[ss]:=x;maxk[ss]:=w;key[ss]:=w;
// id[ss]:=random(maxlongint);
 exit(ss)
end;
procedure ins(s,x,w:longint);inline;
var i:longint;
begin
 i:=s;
 while true do begin
   if w>maxk[i] then maxk[i]:=w;
   if x>d[i] then begin
    if r[i]=0 then begin
     r[i]:=ori(i,x,w);
     i:=r[i];
     break
    end
    else i:=r[i]
   end
   else begin
    if l[i]=0 then begin
      l[i]:=ori(i,x,w);
      i:=l[i];
      break
    end
    else i:=l[i]
   end
 end;
{ while id[i]<id[rt[i]] do
  if l[rt[i]]=i then right(i) else left(i);}
end;
procedure change(x,w:longint);inline;
var y:longint;
begin
 y:=x;x:=a[x].y+m1;
 while x<>0 do begin
   ins(x,a[y].z,w);
   x:=x>>1
 end;
end;
function search(s,w:longint ): longint;inline;
var i,maxf:longint;
begin
  i:=r[s];
  maxf:=0;
  while i<>0 do begin
   if d[i]<w then begin
    maxf:=max(maxf,max(key[i],maxk[l[i]]));
    i:=r[i]
   end
   else if d[i]>w then begin
    i:=l[i]
   end
   else begin
    maxf:=max(maxf,max(key[i],maxk[l[i]]));
    break
   end
  end;
 exit(maxf)
end;
function find(l,r,i:longint ): longint;inline;
var cos:longint;
begin
  l:=l+m1-1;r:=r+m1+1;find:=0;
  while not(l xor r=1) do begin
    if l and 1=0 then begin
      cos:=search(l+1,a[i].z);
      if cos>find then find:=cos
    end;
    if r and 1=1 then begin
      cos:=search(r-1,a[i].z);
      if cos>find then find:=cos
    end;
    l:=l>>1;r:=r>>1
  end;
end;
procedure origin; inline;
var i:longint;
begin
 m1:=1;
 while m1<=n+2 do m1:=m1<<1;
 for i:=1 to n+m1 do begin
   id[i]:=-maxlongint;
   d[i]:=-maxlongint;
   rt[i]:=i
 end;
 ss:=n+m1
end;
procedure qsort(l,r:longint);inline;
var i,j,x:longint;
    c:rex;
begin
 i:=l;j:=r;x:=a[(l+r)>>1].x;
 repeat
  while a[i].x<x do inc(i);
  while x<a[j].x do dec(j);
  if not(i>j) then begin
   c:=a[i];a[i]:=a[j];a[j]:=c;
   inc(i);dec(j)
  end
 until i>j;
 if i<r then qsort(i,r);
 if l<j then qsort(l,j)
end;
procedure init;
var i,x:longint;
begin
 readln(n);
 origin;
 for i:=1 to n do begin read(x);a[x].x:=i end;
 for i:=1 to n do begin read(x);a[x].y:=i end;
 for i:=1 to n do begin read(x);a[x].z:=i end;
 qsort(1,n);
 origin;
 for i:=1 to n do begin
  f[i]:=find(1,a[i].y-1,i)+1;
  if i<>n then change(i,f[i]);
 end;
 ans:=0;
 for i:=1 to n do if f[i]>ans then ans:=f[i];
 writeln(ans)
end;
begin
  inf;
  randomize;
  init;
  ouf
end.                         

update:14.6.25
cdq分治
第1次元は先に並べ替えて、第2次元を処理する時、各区間[l,r]に対して、処理する時[1,l-1]の影響がすべてすでに処理したことを保証して、それから先に[l,mid]を再帰処理して、[mid+1,r]が影響を生むことができないため、その後第2次元の順序を通じて[l,mid]が[mid+1,r]に対する影響を順次処理して、第3次元は第2次元の列挙の時にデータ構造で維持して、次に[mid+1,r]を再帰的に処理する.
2 D目を列挙したくない場合は、集計で行うことができます.[l,r]の処理が完了するたびに、2 D目で順序付けされたシーケンスに集計されます.

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
int Max[200000],u[200000],p[20][200000],f[200000];
int n,a[200000][3],t[200000],w_time;
void change(int x,int w)
{
	for (;x<=n;x+=(x & -x))	
		if (t[x]!=w_time) {
			t[x]=w_time;
			Max[x]=w;
		}
		else Max[x]=max(Max[x],w);
}
int ask(int x)
{
	int sum=0;
	for (;x;x-=(x & -x))
		if (t[x]==w_time) sum=max(sum,Max[x]);
	return sum;
}
bool fl[200000];
bool cmp1(int i,int j)
{
	return a[i][1]<a[j][1];
}
void calc(int e,int l,int r)
{
	if (l==r) return ;
	int mid=(l+r)>>1;
	calc(e+1,l,mid);
	w_time++;
	for (int i=l;i<=r;i++) 
		p[e][i]=u[i],fl[u[i]]=(i<=mid);
	sort(p[e]+l,p[e]+r+1,cmp1);
	for (int i=l;i<=r;i++)
		if (fl[p[e][i]]) change(a[p[e][i]][2],f[p[e][i]]);
		else f[p[e][i]]=max(f[p[e][i]],ask(a[p[e][i]][2])+1);
	calc(e+1,mid+1,r);
	//for (int i=l;i<=r;i++) u[i]=p[e][i];
}
bool cmp(int i,int j)
{
	return a[i][0]<a[j][0];
}
int main()
{
	freopen("godfarmer.in","r",stdin);
	freopen("godfarmer.out","w",stdout);
	scanf("%d",&n);
	for (int e=0;e<=2;e++)
		for (int i=1;i<=n;i++) {
			int x;
			scanf("%d",&x);
			a[x][e]=i;
		}
	for (int i=1;i<=n;i++) u[i]=i;
	sort(u+1,u+n+1,cmp);
	for (int i=1;i<=n;i++) f[i]=1;
	calc(0,1,n);
	int ans=0;
	for (int i=1;i<=n;i++) 
		ans=max(ans,f[i]);
//	for (int i=1;i<=n;i++) cout<<f[i]<<' ';cout<<endl;
	printf("%d
",ans);
	return 0;
}