线段树。
题意：平面上有许多点，每个点有一个权值。给定一个大小确定的矩形，边与x，y轴平行，平移这个矩形能圈住的点的权值之和最大是多少。
注意：矩形边上的不算，所以应该把矩形缩小一点。数据范围会超int，建议用long long
做法：
先把题目转化一下，用矩形的中心点来描述这个矩形的位置。并对每个点建立一个矩形中心点的活动范围，即矩形中心点在这个范围内即可覆盖到该点，建立方法就是以每个点为中心画一个与题中矩形大小相等的矩形。现在点变成了矩形，矩形变成了点。我们要求的是找一个位置来放这个点使得它在最多的矩形内部，即该点的矩形重叠层数最多。
这样我们就可以用线段树来解决了，用一条与y轴平行的扫描线，从左到右来扫描这个矩形重叠图。这条扫描线就是线段树中的整条线段区间，在一个时刻这个线段的不同位置被覆盖了不同层数的矩形，对每次扫描线产生变化后（扫入某一矩形或扫出某一矩形后）求现在正在扫的矩形在线段上覆盖的最大层数。
代码：
#include<stdio.h>
#include<string.h>
#include<iostream>
#include<algorithm>
using namespace std;
#define maxn 110000
#define LL long long
struct list
{
LL l,r,x,val;
} node[maxn*6];
struct liss
{
LL x;
LL y1,y2;
LL c,val;
} line[maxn*2];
LL lines;
LL yy[maxn];
LL a[maxn],b[maxn],c[maxn];
LL sk;
LL n,W,H;
LL maxx;
int cmp(struct liss a,struct liss b)
{
if(a.x!=b.x)return a.x<b.x;
return a.val>b.val;
}
LL search(LL x)
{
LL l=0;
LL r=sk;
LL mid=(l+r)/2;
while(l<r)
{
if(yy[mid]==x)return mid;
if(yy[mid]>x)r=mid;
if(yy[mid]<x)l=mid+1;
mid=(l+r)/2;
}
}
void build(LL l,LL r,int st)
{
LL mid=(l+r)/2;
node[st].l=l;
node[st].r=r;
node[st].x=0;
node[st].val=0;
if(l!=r)
{
build(l,mid,st*2);
build(mid+1,r,st*2+1);
}
}
void insert(LL l,LL r,LL val,int st)
{
LL ll=node[st].l;
LL rr=node[st].r;
if(l>rr||r<ll)return;
if(l<=ll&&rr<=r)
{
node[st].x+=val;
node[st].val+=val;
return ;
}
insert(l,r,val,st*2);
insert(l,r,val,st*2+1);
node[st].val=max(node[st*2].val,node[st*2+1].val)+node[st].x;
}
int main()
{
LL i;
while(~scanf("%lld%lld%lld",&n,&W,&H))
{
LL sy=0;
LL yy1,yy2,xx1,xx2;
for(i=0; i<n; i++)
{
scanf("%lld%lld%lld",&a[i],&b[i],&c[i]);
yy1=b[i];
yy[sy++]=yy1;
yy2=b[i]+H-1;
yy[sy++]=yy2;
}
if(W==0||H==0)
{
cout<<"0"<<endl;
continue;
}
H--,W--;
sort(yy,yy+sy);
sk=1;
for(i=1; i<sy; i++)if(yy[i]!=yy[i-1])yy[sk++]=yy[i];
lines=0;
for(i=0; i<n; i++)
{
yy2=b[i]+H;
yy1=b[i];
xx2=a[i]+W;
xx1=a[i];
yy1=search(yy1);
yy2=search(yy2);
line[lines].x=xx1;
line[lines].y1=yy1;
line[lines].y2=yy2;
line[lines++].val=c[i];
line[lines].x=xx2;
line[lines].y1=yy1;
line[lines].y2=yy2;
line[lines++].val=-c[i];
}
sort(line,line+lines,cmp);
build(0,sk,1);
maxx=0;
for(i=0; i<lines; i++)
{
insert(line[i].y1,line[i].y2,line[i].val,1);
maxx=max(maxx,node[1].val);
}
cout<<maxx<<endl;
}
return 0;
}