基本思想：
- 扫描线
注意点：
- 线段树建树时开大一点没坏处.
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#define int long long
#define ll long long
using namespace std;
const int MAXN=8e6,root=1;
struct Node{
int l,r;
ll lazy,maxx;
void reset(){
l=r=lazy=maxx=0;
}
}tr[MAXN];
void build(int p,int l,int r){
tr[p].reset();
tr[p].l=l,tr[p].r=r;
if(l==r)return;
int mid=(l+r)>>1;
if(l<=mid)build(p<<1,l,mid);
if(r>mid)build((p<<1)|1,mid+1,r);
}
void change(int p,int l,int r,int val){
if(tr[p].l>=l&&tr[p].r<=r){
tr[p].lazy+=val;
tr[p].maxx+=val;
return;
}
if(tr[p].lazy){
tr[p<<1].lazy+=tr[p].lazy;
tr[p<<1].maxx+=tr[p].lazy;
tr[(p<<1)|1].lazy+=tr[p].lazy;
tr[(p<<1)|1].maxx+=tr[p].lazy;
tr[p].lazy=0;
}
int mid=(tr[p].l+tr[p].r)>>1;
if(l<=mid)change(p<<1,l,r,val);
if(r>mid)change((p<<1)|1,l,r,val);
tr[p].maxx=max(tr[p<<1].maxx,tr[(p<<1)|1].maxx);
}
struct Star{
ll x;//横轴坐标
int l,r;//y1 y2位置
ll c;//亮度
bool operator <(Star another)const{
return x==another.x?c<another.c:x<another.x;
}
}stars[MAXN];
ll b[MAXN],yCnt=0;//y坐标离散化
void init(){
memset(b,0,sizeof(b));
yCnt=0;
}
signed main(){
int t;
scanf("%d",&t);
ll n,w,h;
while(cin>>n>>w>>h){
init();
for(int i=1;i<=n;i++){
ll x,y,c;
scanf("%lld%lld%lld",&x,&y,&c);
stars[i].x=x,stars[i+n].x=x+w;
stars[i].l=stars[i+n].l=y;
stars[i].r=stars[i+n].r=y+h-1;
stars[i].c=c,stars[i+n].c=-c;
b[++yCnt]=y,b[++yCnt]=y+h-1;
}
//离散化
sort(b+1,b+yCnt+1);
int bCnt=unique(b+1,b+yCnt+1)-(b+1);//去重
n=2*n;
for(int i=1;i<=n;i++){
stars[i].l=lower_bound(b+1,b+yCnt+1,stars[i].l)-b;
stars[i].r=lower_bound(b+1,b+yCnt+1,stars[i].r)-b;
}
sort(stars+1,stars+n+1);
build(root,1,bCnt*2);
ll ans=0;
for(int i=1;i<=n;i++){
change(root,stars[i].l,stars[i].r,stars[i].c);
ans=max(ans,tr[root].maxx);
}
printf("%lld
",ans);
}
return 0;
}