学步园

【题意】

前面是一段英文情书

给定n个星星的坐标和亮度，求一个位置任意w*h的矩形内最大亮度和（矩形下边界和左边界上的星星不算）

【输入】

多组数据

每组数据开头一行为三个数字n（n<=10000），w，h

接下来n行分别为该星星的横纵坐标和亮度（longint级）

【输出】

对于每组数据输出一个数字表示最大亮度和

求任意一块面积内的亮度和非常麻烦，这题用到了一个转化

对于一个坐标为x,y的亮度为b的星星，在x,y+h的位置添加一个-b的星星

按y值从小到大将星星一行一行的插入，然后这道题就转化为了求最大元素的问题

需要注意y+h会超过longint级

因为x的跨度比较大，所以最好离散一下

program poj2482;
type
  arr=array [0..20001] of int64;
var
  n,w,h,i,j,k,all,tot:longint;
  ans:int64;
  num,xl,dl,b,x,y:arr;
  maxn:array [0..300001] of int64;
  change,left,right:array [0..300001] of longint;

procedure build ;
begin
  inc(tot);
  left[tot]:=0;
  right[tot]:=0;
  change[tot]:=0;
  maxn[tot]:=0;
end;

procedure down (now:longint);
begin
  if left[now]=0 then
    begin
      build;
      left[now]:=tot;
    end;
  if right[now]=0 then
    begin
      build;
      right[now]:=tot;
    end;
  if change[now]=0 then exit;
  maxn[left[now]]:=maxn[left[now]]+change[now];
  change[left[now]]:=change[left[now]]+change[now];
  maxn[right[now]]:=maxn[right[now]]+change[now];
  change[right[now]]:=change[right[now]]+change[now];
  change[now]:=0;
end;

function quick (now:longint):longint;
var
  s,e,mid:longint;
begin
  s:=now;
  e:=all;
  while s<>e do
    begin
      mid:=s+e-(s+e) div 2;
      if num[mid]-num[now]<w then s:=mid
                             else e:=mid-1;
    end;
  exit(s);
end;

procedure swap (var a,b:int64);
var
  i:int64;
begin
  i:=a;
  a:=b;
  b:=i;
end;

procedure qsort (s,e:longint;var x,dl:arr);
var
  i,j:longint;
  k:int64;
begin
  if s>=e then exit;
  i:=s;
  j:=e;
  k:=x[dl[(s+e) div 2]];
  while i<=j do
    begin
      while x[dl[i]]<k do inc(i);
      while x[dl[j]]>k do dec(j);
      if i>j then break;
      swap(dl[i],dl[j]);
      inc(i);
      dec(j);
    end;
  qsort(s,j,x,dl);
  qsort(i,e,x,dl);
end;

function hash (p:int64):int64;
var
  mid,s,e:longint;
begin
  s:=1;
  e:=all;
  repeat
    mid:=(s+e) div 2;
    if p=num[mid] then exit(mid)
                  else
    if p>num[mid] then s:=mid+1
                  else e:=mid-1;
  until false;
end;

procedure insert (s,e,p,l,r,now:longint);
var
  mid:longint;
begin
  if (s=l)and(e=r) then
    begin
      maxn[now]:=maxn[now]+p;
      change[now]:=change[now]+p;
      exit;
    end;
  mid:=(l+r) div 2;
  down(now);
  if e<=mid then
    insert(s,e,p,l,mid,left[now])
            else
  if s>mid then
    insert(s,e,p,mid+1,r,right[now])
           else
    begin
      insert(s,mid,p,l,mid,left[now]);
      insert(mid+1,e,p,mid+1,r,right[now]);
    end;
  if maxn[left[now]]>maxn[right[now]] then maxn[now]:=maxn[left[now]]
                                      else maxn[now]:=maxn[right[now]]
end;

begin
  while not seekeof do
    begin
      read(n,w,h);
      for i:=1 to n do
        begin
          read(x[i],y[i],b[i]);
          x[i+n]:=x[i];
          y[i+n]:=y[i]+h;
          b[i+n]:=-b[i];
        end;
      n:=n*2;
      for i:=1 to n do
        dl[i]:=i;
      for i:=1 to n do
        xl[i]:=i;
      qsort(1,n,y,dl);
      qsort(1,n,x,xl);
      x[xl[0]]:=-100000;
      k:=0;
      all:=0;
      for i:=1 to n do
        if x[xl[i]]<>x[xl[k]] then
          begin
            inc(all);
            num[all]:=x[xl[i]];
            k:=i;
          end;
      k:=1;
      i:=1;
      ans:=0;
      tot:=-1;
      build;
      repeat
        while (i<=n)and(y[dl[i]]=y[dl[k]]) do
          begin
            insert(hash(x[dl[i]]),quick(hash(x[dl[i]])),b[dl[i]],1,all,0);
            inc(i);
          end;
        if maxn[0]>ans then ans:=maxn[0];
        k:=i;
      until i>n;
      writeln(ans);
    end;
end.