QMAX2 - Giá trị lớn nhất ver2

Tác giả: ll931110

Ngôn ngữ: Pascal

{$MODE DELPHI}
Program QMAX2_2;
Uses math;
Const
  input  = '';
  output = '';
  maxn = 50000;
Type
  rec = record
    ins,und: integer;
  end;
Var
  fi,fo: text;
  n,m,u,v,k: integer;
  a: array[1..8 * maxn] of rec;

Procedure openfile;
Begin
  Assign(fi, input);
    Reset(fi);

  Assign(fo, output);
    Rewrite(fo);
End;

Procedure update(i,low,high: integer);
Var
  mid: integer;
Begin
  If (v < low) or (high < u) then exit;
  If (u <= low) and (high <= v) then
    Begin
      inc(a[i].ins,k);
      exit;
    End;

  mid:= (low + high) div 2;
  update(2 * i,low,mid);
  update(2 * i + 1,mid + 1,high);

  a[i].und:= max(a[2 * i].ins + a[2 * i].und,a[2 * i + 1].ins + a[2 * i + 1].und);
End;

Function calc(i,low,high: integer): integer;
Var
  mid: integer;
Begin
  If (v < low) or (high < u) then exit(0);
  If (u <= low) and (high <= v) then exit(a[i].ins + a[i].und);

  mid:= (low + high) div 2;
  calc:= max(calc(2 * i,low,mid),calc(2 * i + 1,mid + 1,high)) + a[i].ins;
End;

Procedure swap(var x,y: integer);
Var
  t: integer;
Begin
  t:= x;
  x:= y;
  y:= t;
End;

Procedure solve;
Var
  i,q: integer;
Begin
  Fillchar(a, sizeof(a), 0);

  Readln(fi, n, m);
  For i:= 1 to m do
    begin
      Read(fi, q, u, v);
      If u > v then swap(u,v);
      If q = 0 then
        Begin
          Readln(fi, k);
          update(1,1,n);
        End
      else writeln(fo, calc(1,1,n));
    End;
End;

Procedure closefile;
Begin
  Close(fo);
  Close(fi);
End;

Begin
  openfile;
  solve;
  closefile;
End.

Download