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.

Download