KGSS - Maximum Sum
Tác giả: RR
Ngôn ngữ: Pascal
{$R+,Q+}
uses math;
const
FINP='';
FOUT='';
MAXN=100000;
snode=262144;
oo=1000000001;
var
f1,f2:text;
n:longint;
a:array[0..MAXN] of longint;
max1,max2:array[1..snode] of longint;
procedure openF; inline;
begin
assign(f1,FINP); reset(f1);
assign(f2,FOUT); rewrite(f2);
end;
procedure closeF; inline;
begin
close(f1); close(f2);
end;
procedure inp; inline;
begin
readln(f1,n);
for n:=1 to n do read(f1,a[n]);
a[0]:=-oo;
end;
procedure build(i,l,r:longint); inline;
var
mid:longint;
begin
if (l=r) then
begin
max1[i]:=l;
max2[i]:=0;
exit;
end;
mid:=(l+r)>>1;
build(i<<1,l,mid);
build(i<<1+1,mid+1,r);
if a[max1[i<<1]]>a[max1[i<<1+1]] then
begin
max1[i]:=max1[i<<1];
if a[max2[i<<1]]>a[max1[i<<1+1]] then max2[i]:=max2[i<<1]
else max2[i]:=max1[i<<1+1];
end
else
begin
max1[i]:=max1[i<<1+1];
if a[max1[i<<1]]>a[max2[i<<1+1]] then max2[i]:=max1[i<<1]
else max2[i]:=max2[i<<1+1];
end;
end;
function get(u,v:longint):longint;
var
m1,m2:longint;
procedure visit(i,l,r:longint); inline;
var
mid:longint;
begin
if l>r then exit;
if (u<=l) and (r<=v) then
begin
if a[max1[i]]>m1 then
begin
m2:=m1; m1:=a[max1[i]];
if a[max2[i]]>m2 then m2:=a[max2[i]];
end
else if a[max1[i]]>m2 then m2:=a[max1[i]];
exit;
end;
if (v<l) or (r<u) then exit;
mid:=(l+r)>>1;
visit(i<<1,l,mid);
visit(i<<1+1,mid+1,r);
end;
begin
m1:=-oo; m2:=-oo;
visit(1,1,n);
get:=m1+m2;
end;
procedure update(u,x:longint);
procedure visit(i,l,r:longint); inline;
var
mid:longint;
begin
if (u<l) or (r<u) then exit;
if (l=r) then
begin
max1[i]:=l; max2[i]:=0;
exit;
end;
mid:=(l+r)>>1;
visit(i<<1,l,mid);
visit(i<<1+1,mid+1,r);
if a[max1[i<<1]]>a[max1[i<<1+1]] then
begin
max1[i]:=max1[i<<1];
if a[max2[i<<1]]>a[max1[i<<1+1]] then max2[i]:=max2[i<<1]
else max2[i]:=max1[i<<1+1];
end
else
begin
max1[i]:=max1[i<<1+1];
if a[max1[i<<1]]>a[max2[i<<1+1]] then max2[i]:=max1[i<<1]
else max2[i]:=max2[i<<1+1];
end;
end;
begin
visit(1,1,n);
end;
procedure ans;
var
q,u,v,x:longint;
ch:char;
begin
readln(f1,q);
for q:=1 to q do
begin
read(f1,ch);
if ch='Q' then
begin
readln(f1,u,v);
writeln(f2,get(u,v));
end
else //ch='U'
begin
readln(f1,u,x); a[u]:=x;
update(u,x);
end;
end;
end;
begin
openF;
inp;
build(1,1,n);
ans;
closeF;
end.