QMAX - Giá trị lớn nhất

Tác giả: ll931110

Ngôn ngữ: Pascal

{$MODE DELPHI}
Program QMAX1_3;
Uses math;
Const
  input  = '';
  output = '';
  maxn = 50000;
Type
  rec = record
    ins,und: integer;
  end;
Var
  fi,fo: text;
  n,m,p: integer;
  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: integer;
Begin
  Fillchar(a, sizeof(a), 0);

  Readln(fi, n, m);
  For i:= 1 to m do
    Begin
      Readln(fi, u, v, k);
      If u > v then swap(u,v);
      update(1,1,n);
    End;

  Readln(fi, p);
  For i:= 1 to p do
    Begin
      Readln(fi, u, v);
      If u > v then swap(u,v);
      Writeln(fo, calc(1,1,n));
    End;
End;

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

Begin
  openfile;
  solve;
  closefile;
End.

Download