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.

Download