NKLP - Hoán vị dài nhất

Tác giả: khuc_tuan

Ngôn ngữ: Pascal

const
fin = '';
fout= '';
maxn= 100001;
type
arr1 = array[1..maxn] of longint ;
var
fi, fo : text ;
vt1, a, back : arr1 ;
maxb, maxa : arr1 ;
result, n : longint ;
procedure nhap;
var
i : longint ;
begin
assign( fi, fin);
reset( fi);
read( fi, n);
for i:=1 to n do read( fi, a[i]);
close( fi);
end;
procedure init_back;
var
i : longint ;
begin
for i:=1 to n do
begin
back[i] := vt1[a[i]];
vt1[a[i]] := i;
end;
end;
procedure ii( var max, pos : arr1 );
var
i,l,r,g : longint ;
begin
for i:=1 to n do
begin
l := 1;
r := n;
while l<=r do
begin
g := (l+r) div 2;
if max[g]<pos[i] then max[g] := pos[i];
if g<i then l := g+1
else if g>i then r := g-1
else break;
end;
end;
end;
function getmax( var max, pos : arr1; x, y : longint ) : longint ;
var res : longint ;
procedure getmax2( l, r : longint );
var
g : longint ;
begin
if l>r then exit;
g := (l+r) div 2;
if (x<=l) and (r<=y) then
begin
if res<max[g] then res := max[g];
exit;
end;
if (x<=g) and (g<=y) then
if res<pos[g] then res := pos[g];
if (x<g) then getmax2( l, g-1);
if (g<y) then getmax2( g+1, r);
end;
begin
res := 0;
getmax2( 1, n);
getmax := res ;
end;
function getindexmax( x, y, mm : longint ) : longint ;
var ind : longint ;
procedure gg( l, r : longint);
var
g : longint ;
begin
if l>r then exit;
if ind<>0 then exit;
g := (l+r) div 2;
if (x<=l) and (r<=y) and (maxa[g]<mm) then exit;
if (x<=g) and (g<=y) then
if mm=a[g] then ind := g;
if (x<g) then gg( l, g-1);
if (g<y) then gg( g+1, r);
end;
begin
ind := 0;
gg( 1, n);
getindexmax := ind;
end;
procedure init_vt1;
var
i : longint ;
begin
vt1[n+1] := n+1;
for i:=n downto 1 do
if a[i]=1 then vt1[i] := i
else vt1[i] := vt1[i+1];
end;
procedure process;
var
t, l, r, g, en, st : longint ;
begin
en := 0;
for st:=1 to n do
begin
if en<st then en := st ;
while (en<n) and (getmax( maxb, back, st, en+1) <st) do inc(en);
g := vt1[st];
l := g;
r := en;
while l<=r do
begin
if r-st+1<=result then break;
t := getmax( maxa, a, st, r);
if t=r-st+1 then
begin
if result<t then result := t;
break;
end;
if t>r-st+1 then
begin
{ if mark[r]<=t then break;
if mark[r]>t then mark[r] := t;}
r := getindexmax( st, r, t) - 1;
end;
end;
end;
end;
procedure xuly;
begin
init_back;
init_vt1;
ii( maxb, back);
ii( maxa, a);
process;
end;
procedure ghi;
begin
assign( fo, fout);
rewrite( fo);
writeln( fo, result);
close( fo);
end;
begin
nhap;
xuly;
ghi;
end.

Download