NKLP - Hoán vị dài nhất
Tác giả: RR
Ngôn ngữ: Pascal
//Written by Nguyen Thanh Trung
//O(N) algorithm
{$R+,Q+}
{$Mode objFPC}
uses math;
const
FINP = '';
FOUT = '';
MAXN = 100111;
type
status = record
left,right : longint;
wrong,ln : longint;
end;
var
f1,f2 : text;
n,kq : longint;
a,dd : array[1..MAXN] of longint;
sum : array[-1..MAXN] of int64;
last,now : status;
procedure openF;
begin
assign(f1,FINP); reset(f1);
assign(f2,FOUT); rewrite(f2);
end;
procedure closeF;
begin
close(f1);
close(f2);
end;
procedure inp;
var
i:longint;
begin
read(f1,n);
for i:=1 to n do
begin
read(f1,a[i]);
sum[i]:=sum[i-1]+a[i];
end;
end;
procedure update;
var
i:longint;
begin
if now.left<1 then now.left:=1;
if now.right>n then now.right:=n;
if last.left<>now.left then
if last.left<now.left then
for i:=last.left to now.left-1 do
begin
dd[a[i]]-=1;
if dd[a[i]]=1 then now.wrong-=1
else if dd[a[i]]=0 then now.wrong+=1;
end
else for i:=last.left-1 downto now.left do
begin
dd[a[i]]+=1;
if dd[a[i]]=1 then now.wrong-=1
else if dd[a[i]]=2 then now.wrong+=1;
end;
if last.right<>now.right then
if last.right>now.right then
for i:=last.right downto now.right+1 do
begin
dd[a[i]]-=1;
if dd[a[i]]=1 then now.wrong-=1
else if dd[a[i]]=0 then now.wrong+=1;
end
else for i:=last.right+1 to now.right do
begin
dd[a[i]]+=1;
if dd[a[i]]=1 then now.wrong-=1
else if dd[a[i]]=2 then now.wrong+=1;
end;
if now.wrong<>0 then exit;
if sum[now.right]-sum[now.left-1]<>(int64(now.ln+1)*now.ln)>>1 then exit;
kq:=max(kq,now.ln);
end; //update
procedure solve;
var
one,x:longint;
save:status;
begin
for one:=1 to n do
if a[one]=1 then
begin
dd[1]:=1;
with save do
begin
left:=one; right:=one;
ln:=1; wrong:=0;
end;
kq:=max(kq,1);
//TH1: so lon nhat o ben trai so 1
last:=save;
x:=one-1;
while (x>=1) and (a[x]<>1) do
begin
with now do
begin
ln:=max(ln,a[x]); wrong:=last.wrong+ln-last.ln;
left:=x; right:=x+ln-1;
end;
x-=1; update;
last:=now;
end;
now:=save; update;
//TH2: so lon nhat o ben phai so 1
last:=save;
x:=one+1;
while (x<=n) and (a[x]<>1) do
begin
with now do
begin
ln:=max(ln,a[x]); wrong:=last.wrong+ln-last.ln;
right:=x; left:=x-ln+1;
end;
x+=1; update;
last:=now;
end;
now:=save; update;
end; //for one
end; //solve
begin
openF;
inp;
kq:=0;
solve;
writeln(f2,kq);
closeF;
end.