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.

Download