KGSS - Maximum Sum
Tác giả: flashmt
Ngôn ngữ: Pascal
uses math;
const fi='';
maxn=100010;
oo=1000000000;
var n,m:longint;
a:array[1..maxn] of longint;
f,g: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=r) and (l=x) then
begin
f[node]:=val; g[node]:=-oo; exit;
end
else
begin
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);
if f[node shl 1]>f[node shl 1+1] then
begin
f[node]:=f[node shl 1];
g[node]:=max(g[node shl 1],f[node shl 1+1]);
end
else
begin
f[node]:=f[node shl 1+1];
g[node]:=max(g[node shl 1+1],f[node shl 1]);
end;
end;
end;
procedure find(node,l,r,x,y:longint;var ff,gg:longint);
var mid,f1,g1,f2,g2:longint;
begin
if (l=x) and (r=y) then
begin
ff:=f[node]; gg:=g[node];
exit;
end;
mid:=(l+r) shr 1;
if y<=mid then
begin
find(node shl 1,l,mid,x,y,ff,gg);
exit;
end;
if x>mid then
begin
find(node shl 1+1,mid+1,r,x,y,ff,gg);
exit;
end;
find(node shl 1,l,mid,x,mid,f1,g1);
find(node shl 1+1,mid+1,r,mid+1,y,f2,g2);
if f1>f2 then
begin
ff:=f1; gg:=max(g1,f2);
end
else
begin
ff:=f2; gg:=max(g2,f1);
end;
end;
procedure pr;
var i,x,y,ff,gg:longint; c:char;
begin
for i:=1 to n do
add(1,1,n,i,a[i]);
readln(m);
for i:=1 to m do
begin
readln(c,x,y);
if c='U' then add(1,1,n,x,y)
else
begin
find(1,1,n,x,y,ff,gg);
writeln(ff+gg);
end;
end;
end;
begin
assign(input,fi); reset(input);
rf;
pr;
close(input);
end.