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.

Download