GSS - Đoạn con có tổng lớn nhất
Tác giả: flashmt
Ngôn ngữ: Pascal
uses math;
const maxn=50010;
oo=1000000000;
var n,m:longint;
a:array[1..maxn] of longint;
f,g,h,s:array[1..maxn shl 2] of longint;
procedure rf;
var i:longint;
begin
read(n);
for i:=1 to n do read(a[i]);
end;
procedure add(node,l,r,x,val:longint);
var mid:longint;
begin
if (l=x) and (l=r) then
begin
f[node]:=val; g[node]:=val; h[node]:=val; s[node]:=val;
exit;
end;
mid:=(l+r) shr 1;
if x<=mid then add(node shl 1,l,mid,x,val)
else add(node shl 1+1,mid+1,r,x,val);
f[node]:=max(f[node shl 1],max(f[node shl 1+1],h[node shl 1]+g[node shl 1+1]));
g[node]:=max(g[node shl 1],s[node shl 1]+g[node shl 1+1]);
h[node]:=max(h[node shl 1+1],s[node shl 1+1]+h[node shl 1]);
s[node]:=s[node shl 1]+s[node shl 1+1];
end;
procedure find(node,l,r,x,y:longint;var ff,gg,hh,ss:longint);
var mid,f1,f2,g1,g2,h1,h2,s1,s2:longint;
begin
if (l=x) and (r=y) then
begin
ff:=f[node]; gg:=g[node]; hh:=h[node]; ss:=s[node];
exit;
end;
mid:=(l+r) shr 1;
f1:=-oo; g1:=-oo; h1:=-oo; s1:=0;
f2:=-oo; g2:=-oo; h2:=-oo; s2:=0;
if y<=mid then
begin
find(node shl 1,l,mid,x,y,ff,gg,hh,ss);
exit;
end;
if x>mid then
begin
find(node shl 1+1,mid+1,r,x,y,ff,gg,hh,ss);
exit;
end;
find(node shl 1,l,mid,x,mid,f1,g1,h1,s1);
find(node shl 1+1,mid+1,r,mid+1,y,f2,g2,h2,s2);
ff:=max(f1,max(f2,h1+g2));
gg:=max(g1,s1+g2);
hh:=max(h2,s2+h1);
ss:=s1+s2;
end;
procedure pr;
var i,x,y,ff,gg,hh,ss:longint;
begin
for i:=1 to n do add(1,1,n,i,a[i]);
read(m);
for i:=1 to m do
begin
read(x,y);
find(1,1,n,x,y,ff,gg,hh,ss);
writeln(ff);
end;
end;
begin
rf;
pr;
end.