KGSS - Maximum Sum

Tác giả: ladpro98

Ngôn ngữ: Pascal

program kgss;
uses    math;
type    int =  record
        ma:longint;
        res:longint;
        end;
const   maxN = 100001;
        fi='';
var     t:array[1..4*maxN] of int;
        a:array[1..maxN] of longint;
        c:char;
        i,u,v,n,q:longint;
        inp:text;

procedure input;
var     i:longint;
begin
        assign(inp,fi);
        reset(inp);
        readln(inp,n);
        for i:=1 to n do
        read(inp,a[i]);
        readln(inp);
        readln(inp,q);
end;

procedure update(k,l,r,i:longint);
var     m,x:longint;
begin
        if (l>i) or (r<i) then exit;
        if l=r then
        begin
                t[k].ma:=a[i];
                t[k].res:=low(longint);
                exit;
        end;
        m:=(l+r) shr 1;
        x:=k shl 1;
        update(x,l,m,i);
        update(x or 1, m+1, r,i);
        t[k].ma:=max(t[x].ma,t[x or 1].ma);
        t[k].res:=max(max(t[x].res,t[x or 1].res),t[x].ma+t[x or 1].ma);
end;

function query(k,l,r,i,j:longint):int;
var     rr,left,right:int;
        m,x,y:longint;
begin
        if (l>j) or (r<i) then exit;
        if (l>=i) and (r<=j) then
        begin
                rr.ma:=t[k].ma;
                rr.res:=t[k].res;
                exit(rr);
        end;
        m:=(l+r) shr 1;
        x:=k shl 1;
        y:=x or 1;
        if m<i then exit(query(y,m+1,r,i,j));
        if m>=j then exit(query(x,l,m,i,j));

        left:=query(x,l,m,i,j);
        right:=query(y,m+1,r,i,j);
        rr.ma:=max(left.ma,right.ma);
        rr.res:=max(max(left.res,right.res),left.ma+right.ma);
        exit(rr);
end;

procedure init;
var     i:longint;
begin
        for i:=1 to n do
        update(1,1,n,i);
end;

begin
        input;
        init;
        for i:=1 to q do
        begin
                readln(inp,c,u,v);
                if c='U' then
                begin
                        a[u]:=v;
                        update(1,1,n,u);
                end
                else
                writeln(query(1,1,n,u,v).res);
        end;
        close(inp);
end.

Download