# 刚学扫描线90分求助

@exzang 2020-03-18 22:28 回复

#include<bits/stdc++.h>
using namespace std;
#define ls p<<1
#define rs p<<1|1
typedef long long ll;

const int N=2e5+5;
int L[N<<3],R[N<<3],f[N<<3],cnt,tot;
ll v[N<<3],Y[N<<1],cov[N<<3];
void build(int p,int l,int r){
L[p]=l; R[p]=r; v[p]=0; cov[p]=0;
if(l==r) return;
int mid=(l+r)>>1;
build(ls,l,mid);

build(rs,mid+1,r);

}
void pushup(int p){v[p]=max(v[ls],v[rs]);}
void pushdown(int p){
if(cov[p]){
cov[ls]+=cov[p]; cov[rs]+=cov[p];
v[ls]+=cov[p]; v[rs]+=cov[p];
cov[p]=0;
}
}
void upt(int p,int l,int r,ll c){
if(l<=L[p] && R[p]<=r){
cov[p]+=c; v[p]+=c; return;
}
pushdown(p);
int mid=(L[p]+R[p])>>1;
if(l<=mid) upt(ls,l,r,c);
if(mid+1<=r) upt(rs,l,r,c);
pushup(p);
}
struct Border{

ll x,y1,y2,f;
}a[N<<1];
bool cmp(Border i,Border j){

return (i.x==j.x)?i.f>j.f:i.x<j.x;

}
int main(){
ll x1,y1,x2,y2,W,H,l;
int n,T;
scanf("%d",&T);

while(T--){
scanf("%d%lld%lld",&n,&W,&H); cnt=0;
for(int i=1;i<=n;++i){
scanf("%lld%lld%lld",&x1,&y1,&l); x2=x1+W-1; y2=y1+H-1;
a[++cnt].x=x1; a[cnt].y1=y1; a[cnt].y2=y2; a[cnt].f=l;
Y[cnt]=y1;
a[++cnt].x=x2; a[cnt].y1=y1; a[cnt].y2=y2; a[cnt].f=-l;
Y[cnt]=y2;
}
sort(a+1,a+cnt+1,cmp);
sort(Y+1,Y+cnt+1);
tot=unique(Y+1,Y+cnt+1)-Y-1;
build(1,1,tot);

ll ans=0,l,r,last=0;
for(int i=1;i<=cnt;++i){
l=lower_bound(Y+1,Y+tot+1,a[i].y1)-Y;
r=lower_bound(Y+1,Y+tot+1,a[i].y2)-Y-1;
upt(1,l,r,a[i].f);
ans=max(ans,v[1]);
}
printf("%lld\n",ans);
}

return 0;
}