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.

Download