NKLINEUP - Xếp hàng
Tác giả: khuc_tuan
Ngôn ngữ: Pascal
uses math;
type integer = longint;
var
i,ln, nn, u,v,n, q : integer;
a : array[1..50000] of integer;
ms, ml : array[1..4*50000] of integer;
procedure init(node,l,r:integer);
var
mid : integer;
begin
if l=r then begin
ms[node] := a[l];
ml[node] := a[l];
end
else begin
mid := (l+r) div 2;
init(2*node,l,mid); init(2*node+1,mid+1,r);
ms[node] := min( ms[2*node],ms[2*node+1]);
ml[node] := max( ml[2*node],ml[2*node+1]);
end;
end;
procedure get(node,l,r:integer);
var mid : integer; begin
if (u<=l) and (r<=v) then begin
ln := max( ln, ml[node]);
nn := min( nn, ms[node]);
exit;
end;
mid := (l+r) div 2;
if u<=mid then get(2*node,l,mid);
if(mid<v) then get(2*node+1,mid+1,r);
end;
begin
read( n, q);
for i:=1 to n do read(a[i]);
init(1,1,n);
for i:=1 to q do begin
read(u,v);
ln := 0;
nn := 1000000000;
get( 1, 1, n);
writeln( ln-nn);
end;
end.