QMAX2 - Giá trị lớn nhất ver2
Tác giả: ll931110
Ngôn ngữ: Pascal
{$MODE DELPHI}
Program QMAX2_2;
Uses math;
Const
input = '';
output = '';
maxn = 50000;
Type
rec = record
ins,und: integer;
end;
Var
fi,fo: text;
n,m,u,v,k: integer;
a: array[1..8 * maxn] of rec;
Procedure openfile;
Begin
Assign(fi, input);
Reset(fi);
Assign(fo, output);
Rewrite(fo);
End;
Procedure update(i,low,high: integer);
Var
mid: integer;
Begin
If (v < low) or (high < u) then exit;
If (u <= low) and (high <= v) then
Begin
inc(a[i].ins,k);
exit;
End;
mid:= (low + high) div 2;
update(2 * i,low,mid);
update(2 * i + 1,mid + 1,high);
a[i].und:= max(a[2 * i].ins + a[2 * i].und,a[2 * i + 1].ins + a[2 * i + 1].und);
End;
Function calc(i,low,high: integer): integer;
Var
mid: integer;
Begin
If (v < low) or (high < u) then exit(0);
If (u <= low) and (high <= v) then exit(a[i].ins + a[i].und);
mid:= (low + high) div 2;
calc:= max(calc(2 * i,low,mid),calc(2 * i + 1,mid + 1,high)) + a[i].ins;
End;
Procedure swap(var x,y: integer);
Var
t: integer;
Begin
t:= x;
x:= y;
y:= t;
End;
Procedure solve;
Var
i,q: integer;
Begin
Fillchar(a, sizeof(a), 0);
Readln(fi, n, m);
For i:= 1 to m do
begin
Read(fi, q, u, v);
If u > v then swap(u,v);
If q = 0 then
Begin
Readln(fi, k);
update(1,1,n);
End
else writeln(fo, calc(1,1,n));
End;
End;
Procedure closefile;
Begin
Close(fo);
Close(fi);
End;
Begin
openfile;
solve;
closefile;
End.