GSS - Đoạn con có tổng lớn nhất

Tác giả: ll931110

Ngôn ngữ: Pascal

{$MODE DELPHI}
Program GSS2;
Uses math;
Const
  input  = '';
  output = '';
  maxn = 50000;
  maxv = 100000000000;
Type
  rec = record
    left,right,val: int64;
  end;
Var
  n,m,u,v: integer;
  a,sum: array[0..maxn] of int64;
  q: array[1..8 * maxn] of rec;
  fi,fo: text;

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

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

Procedure init;
Var
  i: integer;
Begin
  Readln(fi, n);
  sum[0]:= 0;

  For i:= 1 to n do
    Begin
      Read(fi, a[i]);
      sum[i]:= sum[i - 1] + a[i];
    End;
End;

Procedure build(i,low,high: integer);
Var
  mid: integer;
Begin
  If low = high then
    Begin
      q[i].left:= a[low];
      q[i].right:= a[low];
      q[i].val:= a[low];
      exit;
    End;

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

  q[i].left:= max(q[2 * i].left,q[2 * i + 1].left + sum[mid] - sum[low - 1]);
  q[i].right:= max(q[2 * i].right + sum[high] - sum[mid],q[2 * i + 1].right);

  q[i].val:= max(q[2 * i].val,q[2 * i + 1].val);
  q[i].val:= max(q[i].val,q[2 * i].right + q[2 * i + 1].left);
End;

Function calc(i,low,high: integer): rec;
Var
  mid: integer;
  x,y,t: rec;
Begin
  t.left:= -maxv;
  t.right:= -maxv;
  t.val:= -maxv;

  If (v < low) or (high < u) then exit(t);
  If (u <= low) and (high <= v) then exit(q[i]);

  mid:= (low + high) div 2;
  x:= calc(2 * i,low,mid);
  y:= calc(2 * i + 1,mid + 1,high);

  t.left:= max(x.left,sum[mid] - sum[low - 1] + y.left);
  t.right:= max(sum[high] - sum[mid] + x.right,y.right);

  t.val:= max(x.val,y.val);
  If t.val < x.right + y.left then t.val:= x.right + y.left;

  calc:= t;
End;

Procedure solve;
Var
  i: integer;
Begin
  Readln(fi, m);
  For i:= 1 to m do
    Begin
      Readln(fi, u, v);
      Writeln(fo, calc(1,1,n).val);
    End;
End;

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

Begin
  openfile;
  init;
  build(1,1,n);
  solve;
  closefile;
End.

Download