KGSS - Maximum Sum
Tác giả: ll931110
Ngôn ngữ: Pascal
{$MODE DELPHI}
Program KGSS2;
Uses math;
Const
input = '';
output = '';
maxn = 100000;
Type
rec = record
n1,n2: integer;
end;
Var
fi,fo: text;
n,m,x,y: integer;
p: array[1..maxn] of integer;
a: array[1..4 * maxn] of rec;
Procedure openfile;
Begin
Assign(fi, input);
Reset(fi);
Assign(fo, output);
Rewrite(fo);
End;
Procedure getmax(i: integer);
Begin
a[i].n1:= max(a[2 * i].n1,a[2 * i + 1].n1);
If a[2 * i].n1 > a[2 * i + 1].n1 then
a[i].n2:= max(a[2 * i].n2,a[2 * i + 1].n1)
else
a[i].n2:= max(a[2 * i + 1].n2,a[2 * i].n1);
End;
Procedure build(i,low,high: integer);
Var
mid: integer;
Begin
If low = high then
Begin
a[i].n1:= p[low];
a[i].n2:= 0;
exit;
End;
mid:= (low + high) div 2;
build(2 * i,low,mid);
build(2 * i + 1,mid + 1,high);
getmax(i);
End;
Procedure update(i,low,high: integer);
Var
mid: integer;
Begin
If low = high then
Begin
p[low]:= y;
a[i].n1:= y;
exit;
End;
mid:= (low + high) div 2;
If x <= mid then update(2 * i,low,mid)
else update(2 * i + 1,mid + 1,high);
getmax(i);
End;
Function calc(i,low,high: integer): rec;
Var
mid: integer;
t,t1,t2: rec;
Begin
t1.n1:= 0;
t1.n2:= 0;
If (y < low) or (high < x) then exit(t1);
If (x <= low) and (high <= y) then exit(a[i]);
mid:= (low + high) div 2;
t1:= calc(2 * i,low,mid);
t2:= calc(2 * i + 1,mid + 1,high);
t.n1:= max(t1.n1,t2.n1);
If t1.n1 > t2.n1 then
t.n2:= max(t1.n2,t2.n1)
else
t.n2:= max(t2.n2,t1.n1);
calc:= t;
End;
Procedure solve;
Var
i: integer;
t: rec;
ch: char;
Begin
Readln(fi, n);
For i:= 1 to n do read(fi, p[i]);
build(1,1,n);
Readln(fi, m);
For i:= 1 to m do
Begin
Readln(fi, ch, x, y);
If ch = 'U' then update(1,1,n) else
Begin
t:= calc(1,1,n);
Writeln(fo, t.n1 + t.n2);
End;
End;
End;
Procedure closefile;
Begin
Close(fi);
Close(fo);
End;
Begin
openfile;
solve;
closefile;
End.