Cod sursa(job #1179566)

Utilizator Mihai_ChihaiMihai Chihai Mihai_Chihai Data 28 aprilie 2014 21:23:27
Problema Arbori de intervale Scor 50
Compilator fpc Status done
Runda Arhiva educationala Marime 1.38 kb
program            arbint;
const nmax=100000;
  var a:array[1..10*nmax] of longint;
      n,m,i,op,x,y,max:longint;
      bufin,bufout:array[1..1 shl 17] of char;

      function maxim(a,b:longint):longint;
       begin
        if a>b then maxim:=a else maxim:=b;
       end;

  procedure update(nod,st,dr,x,y:longint);
    var mij:longint;
   begin
    if (st=dr) then a[nod]:=y
      else begin
        mij:=(st+dr)div 2;
        if x<=mij then update(2*nod,st,mij,x,y)
        else update(2*nod+1,mij+1,dr,x,y);
        a[nod]:=maxim(a[2*nod],a[2*nod+1]);
       end;
  end;

  procedure query(nod,st,dr,x,y:longint);
   var mij:longint;
  begin
    if (x<=st)and(dr<=y) then begin
      if max<a[nod] then maX:=a[nod]  end
      else begin
         mij:=(st+dr)div 2;
         if x<=mij then query(2*nod,st,mij,x,y);

         if y>mij then query(2*nod+1,mij+1,dr,x,y);
      end;
  end;

  begin
  assign(input,'arbint.in');
  assign(output,'arbint.out');
  reset(input);
  rewrite(output);
  settextbuf(input,bufin);
  settextbuf(output,bufout);
  readln(n,m);
  for i:=1 to n do begin read(x); update(1,1,n,i,x); end;

  for i:=1 to m do
    begin
     readln(op,x,y);
     if op=1 then update(1,1,n,x,y)

       else begin
         max:=-1 shl 30;
         query(1,1,n,x,y);
         writeln(max);
         end;
    end;
  close(output);
  end.