NKLINEUP - Xếp hàng
Tác giả: RR
Ngôn ngữ: Pascal
uses math;
var
a:array[1..50111] of longint;
ln,nn:array[1..131072] of longint;
n,q,i,u,v:longint;
procedure init(i,l,r:longint);
var
mid:longint;
begin
if l=r then
begin
ln[i]:=a[l];
nn[i]:=a[l];
exit;
end;
mid:=(l+r) shr 1;
init(i shl 1,l,mid);
init(i shl 1+1,mid+1,r);
ln[i]:=max(ln[i shl 1],ln[i shl 1+1]);
nn[i]:=min(nn[i shl 1],nn[i shl 1+1]);
end;
function getMax(i,l,r,u,v:longint):longint;
var
mid:longint;
begin
if (v<l) or (r<u) then exit(-1);
if (u<=l) and (r<=v) then exit(ln[i]);
mid:=(l+r) shr 1;
exit(max(getMax(i shl 1,l,mid,u,v),
getMax(i shl 1+1,mid+1,r,u,v)));
end;
function getMin(i,l,r,u,v:longint):longint;
var
mid:longint;
begin
if (v<l) or (r<u) then exit(1000111);
if (u<=l) and (r<=v) then exit(nn[i]);
mid:=(l+r) shr 1;
exit(min(getMin(i shl 1,l,mid,u,v),
getMin(i shl 1+1,mid+1,r,u,v)));
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);
writeln(getMax(1,1,n,u,v)-getMin(1,1,n,u,v));
end;
end.