Program Stone;
var i,j,k,l,n,m,xmi,big,sma:longint;
h:array[1..50000]of longint;
tf:array[0..16]of longint;
max,min:array[1..50000,0..16]of longint;
function wmax(a,b:longint):longint;
begin
if a>b then wmax:=a else wmax:=b;
end;
function wmin(a,b:longint):longint;
begin
if a<b then wmin:=a else wmin:=b;
end;
Begin
assign(input,‘lineup.in‘);assign(output,‘lineup.out‘);
reset(input);rewrite(output);
readln(n,m);
for i:=1 to n do
begin
readln(h[i]);
max[i,0]:=h[i];
min[i,0]:=h[i];
end;
for j:=1 to trunc(ln(n)/ln(2)) do
for i:=1 to n do
begin
max[i,j]:=wmax(max[i,j-1],max[i+1 shl (j-1),j-1]);
min[i,j]:=wmin(min[i,j-1],min[i+1 shl (j-1),j-1]);
end;
for i:=1 to m do
begin
readln(j,k);
l:=trunc(ln(k-j+1)/ln(2));
big:=wmax(max[j,l],max[k-1 shl l+1,l]);
sma:=wmin(min[j,l],min[k-1 shl l+1,l]);
writeln(big-sma);
end;
close(input);close(output);
end.
原文：http://www.cnblogs.com/yesphet/p/5236528.html