这道题可以很简单地写出一个二维循环的解法，就是对于每个节点i，往前扫比这个节点高度大的节点，看能扫到哪，往后扫对这个节点高度大的节点，看能扫到哪。这样对于n≤100，000的数据会爆。于是我们可以想到，如果我们是这样处理：即对于节点i，我们并不是找他能扫到哪，而是节点i是哪个节点的最后或者最左的节点。然后就用到神奇的单调队列：首先对于节点i，将i之前比它高的点j全出队，因为此时j不可能扫过i（a[j]>a[i])，然后j能扫到最右的距离就是i了；然后再将此点入队。 一个小东西就是把n+1点的高度弄完0，这样所有点就都比n+1大了……
var s,q,s2,a:array[0..10]of int64; i,j,k,l,r,n:longint; ans:int64; begin while not eof do begin fillchar(s,sizeof(s),0); fillchar(q,sizeof(q),0); read(n); for i:=1 to n do read(a[i]); readln; l:=1; r:=0; for i:=1 to n+1 do begin while (l<=r) and (a[i]<a[q[r]]) do begin s[q[r]]:=i; dec(r); end; inc(r); q[r]:=i; end; l:=1; r:=0; fillchar(q,sizeof(q),0); for i:=n downto 0 do begin while (l<=r) and (a[i]<a[q[r]]) do begin s2[q[r]]:=i; dec(r); end; inc(r); q[r]:=i; end; ans:=0; for i:=1 to n do if (s[i]-s2[i]-1)*a[i]>ans then ans:=(s[i]-s2[i]-1)*a[i]; writeln(ans); end; writeln(‘0‘); readln; end.
var a,b,c,f,ff,s:array[0..1000000]of longint; i,j,k,l,n,m,r:longint; flag:boolean;begin readln(n,l); readln(b[n],a[1]); for i:=2 to n do begin readln(b[i-1],a[i]); dec(l,b[i-1]); end; b[n]:=l; for i:=1 to n do begin c[i]:=a[i]-b[i]; c[i+n]:=c[i]; end; s[0]:=0; for i:=1 to n+n do s[i]:=s[i-1]+c[i]; l:=1; r:=0; flag:=false; for i:=1 to n do begin while (l<=r) and (s[i]<ff[r]) do dec(r); inc(r); ff[r]:=s[i]; f[r]:=i; end; for i:=n to n+n-1 do begin while (f[l]<=i-n) and (l<=r) do inc(l); while (l<=r) and (s[i]<ff[r]) do dec(r); inc(r); ff[r]:=s[i]; f[r]:=i; if s[i-n]<=ff[l] then begin flag:=true; write(i-n+1,‘ ‘); end; end; if flag=false then begin writeln(-1); end;end.
原文：http://www.cnblogs.com/Macaulish/p/6492043.html
