QMAX - Giá trị lớn nhất
Tác giả: flashmt
Ngôn ngữ: Pascal
const fi='';
fo='';
maxn=50000;
var i,x,y,n,val,m,p,re:longint;
a,mx:array[1..maxn shl 2] of longint;
function min(a,b:longint):longint;
begin
if a<b then min:=a else min:=b;
end;
function max(a,b:longint):longint;
begin
if a>b then max:=a else max:=b;
end;
procedure add(node,l,r,x,y:longint);
var mid:longint;
begin
if (l=x) and (r=y) then
begin
a[node]:=a[node]+val;
mx[node]:=mx[node]+val;
end
else
begin
mid:=(l+r) shr 1;
if x<=mid then add(node shl 1,l,mid,x,min(y,mid));
if mid<y then add(node shl 1+1,mid+1,r,max(x,mid+1),y);
mx[node]:=max(mx[node shl 1],mx[node shl 1+1])+a[node];
end;
end;
procedure findmax(node,l,r,x,y:longint;var t:longint);
var mid,u,v:longint;
begin
if (l=x) and (r=y) then t:=mx[node]
else
begin
mid:=(l+r) shr 1; u:=-maxlongint; v:=u;
if x<=mid then findmax(node shl 1,l,mid,x,min(y,mid),u);
if mid<y then findmax(node shl 1+1,mid+1,r,max(x,mid+1),y,v);
t:=max(u,v)+a[node];
end;
end;
begin
assign(input,fi); reset(input);
assign(output,fo); rewrite(output);
readln(n,m);
for i:=1 to m do
begin
readln(x,y,val);
add(1,1,n,x,y);
end;
readln(p);
for i:=1 to p do
begin
readln(x,y);
findmax(1,1,n,x,y,re);
writeln(re);
end;
close(input); close(output);
end.