记录编号	39494	评测结果	AAAAAAAAAA
题目名称	区间权最大	最终得分	100
用户昵称	IMSL77	是否通过	通过
代码语言	Pascal	运行时间	1.142 s
提交时间	2012-07-12 14:31:45	内存使用	5.62 MiB

program max;
type
  integer=longint;
const
  maxn=110000;
var
  n,m,tot,lastl:integer;
  a,b:array[1..maxn] of integer;
  w:array[1..maxn] of integer;
  l,r:array[1..maxn] of integer;
  ans:array[1..maxn] of integer;
  ind:array[1..maxn] of integer;
  cr,dr:array[1..maxn shl 1] of integer;
  tmax:array[0..maxn shl 1] of integer;

  procedure Fopen;
  begin
    assign(input,'max.in'); reset(input);
    assign(output,'max.out'); rewrite(output);
  end;

  procedure Fclose;
  begin
    close(input); close(output);
  end;

  procedure Init;
  var
    i:integer;
  begin
    readln(n,m);
    for i:=1 to n do readln(a[i],b[i],w[i]);
    for i:=1 to m do readln(l[i],r[i]);
  end;

  procedure QSort1(l,r:integer);
  var
    i,j:integer;
    t,x:integer;
    dt:integer;
  begin
    i:=l; j:=r;
    x:=a[(l+r) shr 1];
    repeat
      while a[i]<x do inc(i);
      while a[j]>x do dec(j);
      if i<=j then
      begin
        t:=a[i]; a[i]:=a[j]; a[j]:=t;
        t:=b[i]; b[i]:=b[j]; b[j]:=t;
        dt:=w[i]; w[i]:=w[j]; w[j]:=dt;
        inc(i); dec(j);
      end;
    until i>j;
    if l<j then QSort1(l,j);
    if i<r then QSort1(i,r);
  end;

  procedure QSort2(tl,tr:integer);
  var
    i,j:integer;
    t,x:integer;
  begin
    i:=tl; j:=tr;
    x:=l[ind[(tl+tr) shr 1]];
    repeat
      while l[ind[i]]>x do inc(i);
      while l[ind[j]]<x do dec(j);
      if i<=j then
      begin
        t:=ind[i]; ind[i]:=ind[j]; ind[j]:=t;
        inc(i); dec(j);
      end;
    until i>j;
    if tl<j then QSort2(tl,j);
    if i<tr then QSort2(i,tr);
  end;

  procedure QSort3(l,r:integer);
  var
    i,j:integer;
    t,x:integer;
  begin
    i:=l; j:=r;
    x:=cr[(l+r) shr 1];
    repeat
      while cr[i]<x do inc(i);
      while cr[j]>x do dec(j);
      if i<=j then
      begin
        t:=cr[i]; cr[i]:=cr[j]; cr[j]:=t;
        inc(i); dec(j);
      end;
    until i>j;
    if l<j then QSort3(l,j);
    if i<r then QSort3(i,r);
  end;

  function bit1(x:integer):integer;
  var
    left,right,mid:integer;
  begin
    left:=1; right:=tot;
    while left<=right do
    begin
      mid:=(left+right) shr 1;
      if dr[mid]=x then exit(mid);
      if dr[mid]<x then left:=mid+1 else right:=mid-1;
    end;
  end;

  function bit2(x:integer):integer;
  var
    left,right,mid:integer;
  begin
    left:=1; right:=n;
    while left<=right do
    begin
      mid:=(left+right) shr 1;
      if x<=a[mid] then right:=mid-1 else left:=mid+1;
    end;
    exit(left);
  end;

  function mmax(a,b:integer):integer;
  begin
    if a<b then exit(b) else exit(a);
  end;

  function lowbit(x:integer):integer;
  begin
    exit(x and (-x));
  end;

  procedure update(k:integer; x:integer);
  begin
    while k<=tot do
    begin
      tmax[k]:=mmax(tmax[k],x);
      inc(k,lowbit(k));
    end;
  end;

  function query(k:integer):integer;
  var
    res:integer;
  begin
    res:=0;
    while k>0 do
    begin
      res:=mmax(res,tmax[k]);
      dec(k,lowbit(k));
    end;
    exit(res);
  end;

  function Answer(l,r:integer):integer;
  var
    i,pl:integer;
  begin
    pl:=bit2(l);
    for i:=pl to lastl-1 do update(bit1(b[i]),w[i]);
    lastl:=pl;
    exit(query(r));
  end;

  procedure Solve;
  var
    i:integer;
  begin
    QSort1(1,n);
    for i:=1 to m do ind[i]:=i;
    QSort2(1,m);
    for i:=1 to m do cr[i]:=r[i];
    for i:=1 to n do cr[i+m]:=b[i];
    QSort3(1,m+n);
    tot:=1; dr[1]:=cr[1];
    for i:=2 to m+n do if cr[i]<>cr[i-1] then
    begin inc(tot); dr[tot]:=cr[i]; end;
    fillchar(tmax,sizeof(tmax),0);
    lastl:=n+1;
    for i:=1 to m do ans[ind[i]]:=Answer(l[ind[i]],bit1(r[ind[i]]));
    for i:=1 to m do writeln(ans[i]);
  end;

begin
  Fopen;
  Init;
  Solve;
  Fclose;
end.