P1699:[Usaco2007Jan]BalancedLineup排队

 1 var n,i,j,q,f,t,times:longint;  2 hmin,hmax:array[0..100,0..50000] of longint;  3 function min(a,b:longint):longint;  4 begin  5   if a>b then exit(b)  6     else exit(a);  7 end;  8 function max(a,b:longint):longint;  9 begin 10   if a>b then exit(a) 11     else exit(b); 12 end; 13 begin 14  readln(n,q); 15   for i:=1 to n do
16  begin 17       readln(hmax[0,i]); 18       hmin[0,i]:=hmax[0,i]; 19  end; 20   for i:=1 to trunc(ln(n)/ln(2))+1 do
21     for j:=1 to n-(1 shl i)+1 do
22  begin 23         hmin[i,j]:=min(hmin[i-1,j],hmin[i-1,j+(1 shl (i-1))]); 24         hmax[i,j]:=max(hmax[i-1,j],hmax[i-1,j+(1 shl (i-1))]); 25  end; 26   for i:=1 to q do
27  begin 28  readln(f,t); 29       times:=trunc(ln(t-f+1)/ln(2)); 30       writeln(max(hmax[times,f],hmax[times,t-(1 shl times)+1])-
31               min(hmin[times,f],hmin[times,t-(1 shl times)+1])); 32  end; 33 end.