仅过第一个点…… 其余WA
#include<bits/stdc++.h>
#define int long long
#define ls(x) x<<1
#define rs(x) x<<1|1
using namespace std;
int const N=1e5+100;
struct Line{
int x,y1,y2;
int val;
};
Line L[N];
bool cmp(Line a,Line b){
if(a.x!=b.x) return a.x<b.x; //按x排序
if(a.val>0 && b.val>0) return a.val>b.val; //同正,则按val大到小排序
return a.val<b.val; //否则让删的在前(先删后增)
}
struct Tree{
int l,r,maxx;
};
Tree t[N<<4];
int n,y[N],T; //y:矩形的y坐标
int W,H,X,Y,val,ans;
void build(int rt,int l,int r){ //离散线段树建树
t[rt].l=y[l]; t[rt].r=y[r];
t[rt].maxx=0;
if(l+1==r){ //叶子宽度为2时退出
return ;
}
int mid=(l+r)>>1;
build(ls(rt),l,mid);
build(rs(rt),mid,r); //▲中间是重叠的
return ;
}
void pushup(int rt){
t[rt].maxx=max(t[ls(rt)].maxx,t[rs(rt)].maxx);
return ;
}
void change(int rt,int ul,int ur,int c){
if(t[rt].l>=ur || t[rt].r<=ul) return ;
if(ul<=t[rt].l && t[rt].r<=ur){
t[rt].maxx+=c;
// pushup(rt); //▲ 这里没有pushup,否则就都成0了
return ;
}
change(ls(rt),ul,ur,c);
change(rs(rt),ul,ur,c);
pushup(rt);
return ;
}
signed main(){
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin>>T;
while(T--){
memset(L,0,sizeof(L));
memset(t,0,sizeof(t));
memset(y,0,sizeof(y));
cin>>n>>W>>H;
for(int i=1;i<=n;i++){
cin>>X>>Y>>val;
L[i]={X,Y,Y+H,val};
L[n+i]={X+W,Y,Y+H,-val};
y[i]=Y; y[n+i]=Y+H;
}
n=n<<1;
sort(L+1,L+n+1,cmp);
sort(y+1,y+n+1);
build(1,1,n);
ans=0; //清空ans
for(int i=1;i<=n;i++){
change(1,L[i].y1,L[i].y2,L[i].val);
ans=max(ans,t[1].maxx);
}
cout<<ans<<endl;
}
return 0;
}