roosephu試験問題の1つ:3 Dバイアス
roosephuの試験問題は、水の問題はやはり水で、難題は難しい.
三次元偏序は、もともと以前の省隊合宿の時に出会ったもので、その時はすっかり吐き気がして、書かなかったが、今回はまだ小さな吐き気になった.
原題は3つの1~nの配列列にあげて、3つの配列の最も長い共通のサブシーケンスを求めます.
3 Dバイアスに変換するのは比較的望ましいが,主な問題はこの気持ち悪い3 Dバイアスがnlog^2(n)の複雑さを達成しなければならないことである.
メンテナンスバイアスの一般的な処理方法はlznツリー/二分集計/ツリー状配列orセグメントツリーであり、1つのものは1次元しか処理できないので、方法は選択できません.1次元(x)ソート、2次元(y)集計、3次元(z)ツリー状配列、簡単なことを言っていますが、実はそうではありません.
ソートして1次元を維持するのは理解しやすいです.主に集計と樹状配列がどのように結合するかである.
x次元をソートして維持した後、再帰的に処理します.
1.区間[L,R]を扱う場合、まず二分区間[L,(L+R)/2]で、この左区間を再帰的に求める(二分の原因はy次元を維持する際にx次元の性質を破壊することは避けられないが、二分後には左区間のxがすべて右区間のxより大きいことを保証できる).
2.このとき左区間y次元は秩序化されているので,右区間[(L+R)/2,R],早く並べ替え,集計式のdp転送(左区間1ポインタ,右区間1ポインタ,左区間1ポインタ,左区間1ポインタ,左区間ポインタが掃いたyが右区間ポインタが掃いたyよりも必ず小さいことを保証する)を行い,従来の木状配列でzを維持するしかない.
3.もちろん,最後に右区間[(L+R)/2,R]をxで速やかに並べ戻し,このセグメントを再帰的に処理すべきである.
4.最後に、区間全体のy秩序を集計または速やかに維持する.
ちょっと葛藤して・・・ツリーを書くと分かりやすいかもしれませんが、定数が大きいので、ここに行ってみてください.
http://blog.csdn.net/huyuncong/article/details/6884287
コードも醜いので、木のカバーツリーほど短くないと思います.
program lmd;
uses math;
type
arr=array[0..100000]of longint;
var
f,a,b,c,d,hp :arr;
bit,time :array[0..200000]of longint;
x,i,n,st,ans,now:longint;
procedure inf;
begin
assign(input,'godfarmer.in');
assign(output,'godfarmer.out');
reset(input); rewrite(output);
end;
procedure ouf;
begin
close(input); close(output);
end;
procedure sort(l,r:longint; var x:arr);
var i,j,xy,tmp:longint;
begin
if l=r then exit;
i:=l; j:=r; xy:=d[(l+r) shr 1];
repeat
while x[d[i]]<x[xy] do inc(i);
while x[d[j]]>x[xy] do dec(j);
if i<=j then
begin
tmp:=d[i]; d[i]:=d[j]; d[j]:=tmp;
inc(i); dec(j);
end;
until i>j;
if i<r then sort(i,r,x);
if l<j then sort(l,j,x);
end;
procedure init;
begin
read(n);
for i:=1 to n do
begin
read(x);
a[x]:=i;
end;
for i:=1 to n do
begin
read(x);
b[x]:=i;
end;
for i:=1 to n do
begin
read(x);
c[x]:=i;
end;
for i:=1 to n do d[i]:=i;
end;
procedure change(x,d:longint);
begin
while x<=n do
begin
if time[x]<>now then
begin
time[x]:=now;
bit[x]:=0;
end;
bit[x]:=max(bit[x],d);
x:=x + x and (-x);
end;
end;
function ask(x:longint):longint;
begin
ask:=0;
while x>0 do
begin
if time[x]=now then
ask:=max(ask,bit[x]);
x:= x- x and (-x);
end;
end;
procedure make(l,r:longint);
var z,i,bi,bj:longint;
begin
if l=r then begin f[d[l]]:=max(1,f[d[l]]); exit; end;
z:=(l+r) shr 1;
make(l,z);
sort(z+1,r,b);
inc(now);
bi:=l-1;
for bj:=z+1 to r do
begin
while (b[d[bi+1]]<b[d[bj]]) and (bi<z) do
begin
inc(bi);
change(c[d[bi]],f[d[bi]]);
end;
f[d[bj]]:=max(f[d[bj]],ask(c[d[bj]])+1);
end;
sort(z+1,r,a);
make(z+1,r);
bi:=l-1;
hp[0]:=0;
for bj:=z+1 to r do
begin
while (b[d[bi+1]]<b[d[bj]]) and (bi<z) do
begin
inc(bi);
inc(hp[0]); hp[hp[0]]:=d[bi];
end;
inc(hp[0]); hp[hp[0]]:=d[bj];
end;
while bi<z do
begin
inc(hp[0]); inc(bi); hp[hp[0]]:=d[bi];
end;
for i:=1 to hp[0] do
d[i+l-1]:=hp[i];
end;
begin
inf;
init;
sort(1,n,a);
make(1,n);
for i:=1 to n do
ans:=max(ans,f[d[i]]);
write(ans);
ouf;
end.