这题考双端队列……好偏门的数据结构……
Program c;
const
maxn=1000000;
type
node=record
num,d:longint;
end;
douq=record
d:array[1..maxn] of node;
l,r:longint;
end;
var
n,k,i,j:longint;
a:array[1..maxn] of longint;
ans1,ans2:array[1..maxn] of longint;
minq,maxq:douq;
procedure push(var q:douq;num2,d2:longint);
begin
with q do
begin
inc(r);
d[q.r].num:=num2;
d[q.r].d:=d2;
end;
end;
procedure popl(var q:douq;i:longint);
begin
with q do
begin
if d[l].num=i then inc(l);
end;
end;
procedure popr(up,i:longint);
var
j:longint;
begin
if up=1 then
begin
with minq do
begin
while (l<r) and (d[r].d>i) do dec(r);
if l=r then
if d[r].d>i then dec(r);
end;
end
else
begin
with maxq do
begin
while (l<r) and (d[r].d<i) do dec(r);
if l=r then
if d[r].d<i then dec(r);
end;
end;
end;
begin
read(n,k);
for i:=1 to n do read(a[i]);
fillchar(minq,sizeof(minq),0);
minq.l:=1;
fillchar(maxq,sizeof(maxq),0);
maxq.l:=1;
if k=1 then
begin
for i:=1 to n-1 do write(a[i],' ');
writeln(a[n]);
for i:=1 to n-1 do write(a[i],' ');
writeln(a[n]);
end
else
begin
for i:=1 to k do
begin
popr(1,a[i]);
push(minq,i,a[i]);
popr(0,a[i]);
push(maxq,i,a[i]);
end;
ans1[1]:=minq.d[minq.l].d;
ans2[1]:=maxq.d[maxq.l].d;
for i:=k+1 to n do
begin
popl(minq,i-k);
popl(maxq,i-k);
popr(1,a[i]);
push(minq,i,a[i]);
popr(0,a[i]);
push(maxq,i,a[i]);
ans1[i-k+1]:=minq.d[minq.l].d;
ans2[i-k+1]:=maxq.d[maxq.l].d;
end;
for i:=1 to n-k do write(ans1[i],' ');
writeln(ans1[n-k+1]);
for i:=1 to n-k do write(ans2[i],' ');
writeln(ans2[n-k+1]);
end;
end.