KGSS - Maximum Sum

Tác giả: khuc_tuan

Ngôn ngữ: Pascal

// {$APPTYPE CONSOLE}
 {$mode delphi}

uses
    Math, SysUtils;

type
    Data = class
        l, u, v : integer;
        constructor init(l,u,v : integer);
        constructor merge(a, b : Data);
    end;

constructor Data.merge(a, b : Data);
begin
    l := 2;
    if a.u > b.u then
    begin
        self.u := a.u;
        if a.l=1 then self.v := b.u
        else self.v := max(a.v,b.u);
    end
    else
    begin
        self.u := b.u;
        if b.l=1 then self.v := a.u
        else self.v := max(a.u,b.v);
    end;
end;

constructor Data.init(l,u,v : integer);
begin
    self.l := l;
    self.v := v;
    self.u := u;
end;

var
    i, u, v, q, n : integer;
    c : char;
    a : array[1..100000] of integer;
    it : array[1..100000 * 4] of Data;
    res : Data;

procedure init(i,l,r : integer);
begin
    if l=r then
    begin
        it[i] := Data.init(1,a[l],0);
    end
    else
    begin
        init(2*i,l,(l+r) div 2);
        init(2*i+1,(l+r) div 2 + 1, r);
        it[i] := Data.merge(it[2*i], it[2*i+1]);
    end;
end;

procedure update(i, l, r, p, v : integer);
var
    m : integer;
begin
    if l=r then
    begin
       a[l] := v;
       it[i] := Data.init(1,a[l],0);
    end
    else
    begin
        m := (l+r) div 2;
        if p <= m then update(2*i, l, m, p, v)
        else update(2*i+1,m+1,r,p,v);
        it[i] := Data.merge(it[2*i],it[2*i+1]);
    end;
end;

procedure travel(i, l, r, x, y : integer);
var
    m : integer;
begin
    if (x <= l) and (r <= y) then
    begin
        if res = nil then res := it[i]
        else res := Data.merge(res, it[i]);
        exit;
    end;
    m := (l+r) div 2;
    if x <= m then travel( 2*i, l, m, x, y);
    if m < y then travel( 2*i+1, m+1, r, x, y);
end;

begin
    read(n);
    for i:=1 to n do read(a[i]);
    init( 1, 1, n);
    readln(q);
    for i:=1 to q do
    begin
        readln(c,u,v);
        if c='Q' then
        begin
            res := nil;
            travel( 1, 1, n, u, v);
            writeln( res.u + res.v);
        end
        else
        begin
            update( 1, 1, n, u, v);
        end;
    end;
end.

Download