roosephu的考题,水题倒还是水,难题难的无语。
三维偏序,本来是以前省队集训的时候遇到的东西,那时候是彻底被恶心到了,没写出来,而这一次仍旧被小小的恶心到了。
原题是给三个1~n的排列列,求三个排列的最长公共子序列。
转化成三维偏序是比较好想的,而主要问题是这个恶心的三维偏序必须做到nlog^2(n) 的复杂度。
维护偏序一般处理方法是 lzn树/ 二分归并/ 树状数组or线段树,一个东西只能处理一维,所以方法是没得选的,一维(x)排序,二维(y)归并,三维(z)树状数组,说的简单,其实是在不是这么回事。
排序维护第一维是好理解的。主要是归并和树状数组如何结合。
排序维护x维之后,递归处理:
1.在处理区间[L,R]的时候,先二分区间[L, (L+R)/ 2],递归求这个左区间(二分的原因是我在维护y维的时候难免破坏x维的性质,但是二分之后我还是可以保证左区间的x全都大于右区间的x)。
2.这个时候左区间y维已经有序,我们只好把右区间[(L+R)/2,R],快排一遍,进行归并式的dp转移(左区间一个指针,右区间一个指针,保证左区间指针所扫过的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.