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.