rt,扫描线和题解的方向是反的。
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define debug() puts("I WILL AK")
#define N 100007
struct tree{
int mx,lazy;
}tr[N<<2];
int T,n,w,h,tp;
int x[N],y[N],l[N],ck[N<<2];
inline int max(int a,int b){
return a>b?a:b;
}
inline int min(int a,int b){
return a<b?a:b;
}
inline void pushup(int rt){
tr[rt].mx=max(tr[rt<<1].mx,tr[rt<<1|1].mx);
}
inline void pushdown(int rt){
int tg=tr[rt].lazy;
tr[rt<<1].mx+=tg;
tr[rt<<1].lazy+=tg;
tr[rt<<1|1].mx+=tg;
tr[rt<<1|1].lazy+=tg;
tr[rt].lazy=0;
}
void upd(int rt,int l,int r,int ul,int ur,int k){
if(ul<=l&&r<=ur){
tr[rt].mx+=k;
tr[rt].lazy+=k;
return;
}
pushdown(rt);
int mid=(l+r)>>1;
if(ul<=mid) upd(rt<<1,l,mid,ul,ur,k);
if(ur>mid) upd(rt<<1|1,mid+1,r,ul,ur,k);
pushup(rt);
}
int qry(int rt,int l,int r,int ql,int qr){
if(ql<=l&&r<=qr){
return tr[rt].mx;
}
pushdown(rt);
int mid=(l+r)>>1;
if(qr<=mid) return qry(rt<<1,l,mid,ql,qr);
else if(ql>mid) return qry(rt<<1|1,mid+1,r,ql,qr);
else return max(qry(rt<<1,l,mid,ql,qr),qry(rt<<1|1,mid+1,r,ql,qr));
}
struct bl{
int l,r,st,add;
bool operator <(const bl &b) const{
return st<b.st||(st==b.st&&add>b.add);
}
}p[N<<2];
void clear(){
for(int i=0;i<=n*4;++i){
tr[i]={0,0};
p[i]={0,0,0,0};
}
tp=0;
}
signed main(){
//freopen(".in","r",stdin);
//freopen(".out","w",stdout);
cin>>T;
while(T--){
clear();
cin>>n>>w>>h;
for(int i=1;i<=n;++i){
cin>>x[i]>>y[i]>>l[i];
p[++tp]={x[i],x[i]+w-1,y[i],l[i]};
p[++tp]={x[i],x[i]+w-1,y[i]+h-1,-l[i]};
ck[tp-1]=p[tp].l;
ck[tp]=p[tp].r;
}
//(int i=1;i<=tp;++i) printf("i:%d l:%d,r:%d,st:%d,add:%d\n",i,p[i].l,p[i].r,p[i].st,p[i].add);
sort(p+1,p+tp+1);
sort(ck+1,ck+tp+1);
int sum=unique(ck+1,ck+tp+1)-ck-1;
for(int i=1;i<=tp;++i){
p[i].l=lower_bound(ck+1,ck+sum+1,p[i].l)-ck;
p[i].r=lower_bound(ck+1,ck+sum+1,p[i].r)-ck;
}
int ans=0;
for(int i=1;i<=tp;++i){
upd(1,1,sum,p[i].l,p[i].r,p[i].add);
ans=max(ans,tr[1].mx);
//cout<<p[i].st<<' '<<qry(1,1,tp,1,tp)<<'\n';
}
cout<<ans<<'\n';
}
return 0;
}