KGSS - Maximum Sum
Tác giả: ladpro98
Ngôn ngữ: Pascal
program kgss;
uses math;
type int = record
ma:longint;
res:longint;
end;
const maxN = 100001;
fi='';
var t:array[1..4*maxN] of int;
a:array[1..maxN] of longint;
c:char;
i,u,v,n,q:longint;
inp:text;
procedure input;
var i:longint;
begin
assign(inp,fi);
reset(inp);
readln(inp,n);
for i:=1 to n do
read(inp,a[i]);
readln(inp);
readln(inp,q);
end;
procedure update(k,l,r,i:longint);
var m,x:longint;
begin
if (l>i) or (r<i) then exit;
if l=r then
begin
t[k].ma:=a[i];
t[k].res:=low(longint);
exit;
end;
m:=(l+r) shr 1;
x:=k shl 1;
update(x,l,m,i);
update(x or 1, m+1, r,i);
t[k].ma:=max(t[x].ma,t[x or 1].ma);
t[k].res:=max(max(t[x].res,t[x or 1].res),t[x].ma+t[x or 1].ma);
end;
function query(k,l,r,i,j:longint):int;
var rr,left,right:int;
m,x,y:longint;
begin
if (l>j) or (r<i) then exit;
if (l>=i) and (r<=j) then
begin
rr.ma:=t[k].ma;
rr.res:=t[k].res;
exit(rr);
end;
m:=(l+r) shr 1;
x:=k shl 1;
y:=x or 1;
if m<i then exit(query(y,m+1,r,i,j));
if m>=j then exit(query(x,l,m,i,j));
left:=query(x,l,m,i,j);
right:=query(y,m+1,r,i,j);
rr.ma:=max(left.ma,right.ma);
rr.res:=max(max(left.res,right.res),left.ma+right.ma);
exit(rr);
end;
procedure init;
var i:longint;
begin
for i:=1 to n do
update(1,1,n,i);
end;
begin
input;
init;
for i:=1 to q do
begin
readln(inp,c,u,v);
if c='U' then
begin
a[u]:=v;
update(1,1,n,u);
end
else
writeln(query(1,1,n,u,v).res);
end;
close(inp);
end.