JZOJ 4810 【NOIP2016提高A组五校联考1】道路规划

道路规划

题目大意

某王国的北部有n个城市，编号为1~n且互不相同，南部也有n个城市，亦是如此。接下来
这里写图片描述
如图，上面的一行为北部城市，下面的一行为南部城市：

数据范围

这里写图片描述

题解

首先给这些城市重新编号，南部城市的编号从左往右依次为1~n，与其相连的北部城市也要跟着变。
然后接下来我们研究研究以下这种情况，如图为一个可行的城市集合（橙色），若要加上某一组城市（蓝色）（满足这组城市中，在北边的城市比集合中最靠右的北部城市还要靠右），那么这组城市加入集合后，该集合还是一个可行集合当且仅当这组城市中在南部的城市比集合中最靠左的南部城市还要靠左，如图：
这里写图片描述
设Fi表示选了南部城市编号为i的这组城市时包含它的集合最大值（集合中最左的南部城市为i），有了上述结论，转移就很简单了，时间复杂度为n2，转移如下：

F[i]=max(F[j])+1(1<=j<i且No[j]<No[i]且So[j]>So[i])
So[k]表示城市k在南边的位置
No[k]表示城市k在北边的位置

加上个树状数组就可以将时间复杂度降到nlogn了。

Code(Pascal)

var
    dy,tr:array[0..300000] of int64;
    no,so:array[0..120000] of int64;
    n,m,l,i,o:longint;
function max(a,b:int64):int64;
    begin
        if a>b then exit(a)
        else exit(b);
    end;
function lowbit(o:longint):longint;
    begin
        exit(o and (-o));
    end;
function xz(o:longint):longint;
    begin
        xz:=0;
        while o<=n do
        begin
            xz:=max(xz,tr[o]);
            o:=o+lowbit(o);
        end;
    end;
procedure gx(o,k:longint);
    begin
        while o>0 do
        begin
            tr[o]:=max(tr[o],k);
            o:=o-lowbit(o);
        end;
    end;
begin
    readln(n);
    for i:=1 to n do
    begin
        read(so[i]);
        so[i]:=so[i]+n;
    end;
    readln;
    for i:=1 to n do
    begin
        read(no[i]);
        no[i]:=no[i]+n;
        dy[no[i]]:=i;
    end;
    o:=0;
    m:=0;
    for i:=1 to n do
    begin
        o:=xz(dy[so[i]])+1;
        m:=max(m,o);
        gx(dy[so[i]]-1,o);
    end;
    writeln(m);
end.