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.

Download