KGSS - Maximum Sum
Tác giả: khuc_tuan
Ngôn ngữ: Pascal
// {$APPTYPE CONSOLE}
{$mode delphi}
uses
Math, SysUtils;
type
Data = class
l, u, v : integer;
constructor init(l,u,v : integer);
constructor merge(a, b : Data);
end;
constructor Data.merge(a, b : Data);
begin
l := 2;
if a.u > b.u then
begin
self.u := a.u;
if a.l=1 then self.v := b.u
else self.v := max(a.v,b.u);
end
else
begin
self.u := b.u;
if b.l=1 then self.v := a.u
else self.v := max(a.u,b.v);
end;
end;
constructor Data.init(l,u,v : integer);
begin
self.l := l;
self.v := v;
self.u := u;
end;
var
i, u, v, q, n : integer;
c : char;
a : array[1..100000] of integer;
it : array[1..100000 * 4] of Data;
res : Data;
procedure init(i,l,r : integer);
begin
if l=r then
begin
it[i] := Data.init(1,a[l],0);
end
else
begin
init(2*i,l,(l+r) div 2);
init(2*i+1,(l+r) div 2 + 1, r);
it[i] := Data.merge(it[2*i], it[2*i+1]);
end;
end;
procedure update(i, l, r, p, v : integer);
var
m : integer;
begin
if l=r then
begin
a[l] := v;
it[i] := Data.init(1,a[l],0);
end
else
begin
m := (l+r) div 2;
if p <= m then update(2*i, l, m, p, v)
else update(2*i+1,m+1,r,p,v);
it[i] := Data.merge(it[2*i],it[2*i+1]);
end;
end;
procedure travel(i, l, r, x, y : integer);
var
m : integer;
begin
if (x <= l) and (r <= y) then
begin
if res = nil then res := it[i]
else res := Data.merge(res, it[i]);
exit;
end;
m := (l+r) div 2;
if x <= m then travel( 2*i, l, m, x, y);
if m < y then travel( 2*i+1, m+1, r, x, y);
end;
begin
read(n);
for i:=1 to n do read(a[i]);
init( 1, 1, n);
readln(q);
for i:=1 to q do
begin
readln(c,u,v);
if c='Q' then
begin
res := nil;
travel( 1, 1, n, u, v);
writeln( res.u + res.v);
end
else
begin
update( 1, 1, n, u, v);
end;
end;
end.