来自"NOCOW"

type
zy=record
     ind,value:longint;
    end;
var
h:array[0..25001] of zy;
p,m,n,len:longint;
temp:zy;
 
procedure change(var a,b:zy);
var
t:zy;
begin
t:=a;
a:=b;
b:=t;
end;
 
procedure put(x:zy);
var
son:longint;
begin
inc(len);
h[len]:=x;
son:=len;
while (son<>1) and (h[son div 2].value<h[son].value) do
  begin
   change(h[son div 2],h[son]);
   son:=son div 2;
  end;
end;
 
procedure deletetop;
var
son,fa:longint;
stop:boolean;
begin
h[1]:=h[len];
dec(len);
fa:=1;
stop:=false;
while (fa*2<=len) and (not stop) do
  begin
   if (fa*2+1>len) or (h[fa*2].value>h[fa*2+1].value) then
    son:=fa*2
   else
    son:=fa*2+1;
   if h[son].value>h[fa].value then
    begin
     change(h[son],h[fa]);
     fa:=son;
    end
   else
    stop:=true;
  end;
end;
 
begin
readln(m);
n:=0;
len:=0;
while true do
  begin
   readln(p);
   if p=-1 then break;
   inc(n);
   temp.ind:=n;
   temp.value:=p;
   put(temp);
   if n>=m then
    begin
     while h[1].ind<n-m+1 do
      deletetop;
     writeln(h[1].value);
    end;
  end;
end.

//队列做，估计是寂寞哥看太简单了，没写
program sad;
var b,a,p:array[1..30000] of longint;
i,j,k,n,m,t,h,w,o:longint;
f:boolean;
 
 
 
procedure kp(l,h:longint);
var i,j,x,t,tt:longint;
begin
i:=l;
j:=h;
x:=a[(l+h) div 2];
repeat
while a[i]<x do inc(i);
while a[j]>x do dec(j);
if i<=j then
begin
t:=a[i];
a[i]:=a[j];
a[j]:=t;
inc(i);
dec(j);
end;
until i>j;
if i<h then kp(i,h);
if j>l then kp(l,j);
end;
 
 
begin
n:=0;
readln(m);
while j<>-1 do
begin
inc(n);
readln(j);
if j<>-1 then
a[n]:=j;
end;
;
dec(n);
if m>=n then
begin
kp(1,n);
writeln(a[n]);
halt;
end;
 
 
fillchar(p,sizeof(p),128);
j:=1;
t:=1;
h:=1;
p[1]:=a[1];
b[1]:=1;
while j<n do
begin
//inc(h);
//f:=false;
inc(j);
if j>=m then f:=true;
if j-b[h]+1>m then begin
inc(h);
end;
 
w:=a[j];
while (p[t]<w) and (t>=h) do
dec(t);
inc(t);
p[t]:=w;
b[t]:=j;
if f then
writeln(p[h]);
end;
end.//By Gdp.

---

原来是单调队列做啊。。。

之前一直不知道，还写了个zkw版线段树。

不过上面两个代码真没看懂。

#include <cstdio>
#include <cstdlib>
int n,m,a,l=1,r=1,Q[25001]={0},pos[25001]={0};
int main()
{
    scanf("%d",&m);
    for (int i=1;;++i)
    {
        scanf("%d",&a);
        if (a == -1)  break;
        while ((l <= r) && (i-pos[l] >= m))  ++l;
        while ((r >= l) && (Q[r] < a))  --r;
        Q[++r]=a;
        pos[r]=i;
        if (i >= m)  printf("%d\n",Q[l]);
    }
    return 0;
}
//by zzy