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.

Download