NKLINEUP - Xếp hàng
Tác giả: flashmt
Ngôn ngữ: Pascal
const fi='';
fo='';
maxn=50000;
var n,m,p,q,low,high,i:longint;
a:array[1..maxn] of longint;
min,max:array[1..maxn shl 2] of longint;
function getmin(x,y:longint):longint;
begin
if x<y then getmin:=x else getmin:=y;
end;
function getmax(x,y:longint):longint;
begin
if x>y then getmax:=x else getmax:=y;
end;
procedure initmax(node,l,r:longint);
var mid:longint;
begin
if l=r then max[node]:=a[l]
else
begin
mid:=(l+r) shr 1;
initmax(node shl 1,l,mid);
initmax(node shl 1+1,mid+1,r);
max[node]:=getmax(max[node shl 1],max[node shl 1+1]);
end;
end;
procedure initmin(node,l,r:longint);
var mid:longint;
begin
if l=r then min[node]:=a[l]
else
begin
mid:=(l+r) shr 1;
initmin(node shl 1,l,mid);
initmin(node shl 1+1,mid+1,r);
min[node]:=getmin(min[node shl 1],min[node shl 1+1]);
end;
end;
procedure findmin(node,l,r,p,q:longint);
var mid:longint;
begin
if (l=p) and (r=q) then low:=getmin(low,min[node])
else
begin
mid:=(l+r) shr 1;
if p<=mid then findmin(node shl 1,l,mid,p,getmin(mid,q));
if q>mid then findmin(node shl 1+1,mid+1,r,getmax(mid+1,p),q);
end;
end;
procedure findmax(node,l,r,p,q:longint);
var mid:longint;
begin
if (l=p) and (r=q) then high:=getmax(high,max[node])
else
begin
mid:=(l+r) shr 1;
if p<=mid then findmax(node shl 1,l,mid,p,getmin(mid,q));
if q>mid then findmax(node shl 1+1,mid+1,r,getmax(mid+1,p),q);
end;
end;
begin
assign(input,fi); reset(input);
assign(output,fo); rewrite(output);
readln(n,m);
for i:=1 to n do readln(a[i]);
initmin(1,1,n);
initmax(1,1,n);
for i:=1 to m do
begin
readln(p,q);
low:=maxlongint;
high:=-low;
findmin(1,1,n,p,q);
findmax(1,1,n,p,q);
writeln(high-low);
end;
close(input); close(output);
end.