理论上没啥问题,只是理论,只能过样例
#include<bits/stdc++.h>
using namespace std;
const int N = 1e4+10;
#define int long long
int xs[N<<1];
struct lin{
int x1,x2,y,l;
} lines[N<<1];
struct node{
int l,r;
int x1,x2;
int ma,add_tag;
}tre[N<<2];
#define self tre[p]
#define lp p<<1
#define rp p<<1|1
#define ls tre[lp]
#define rs tre[rp]
void push_up(int p){
self.ma = max(ls.ma,rs.ma);
}
void push_down(int p){
ls.add_tag += self.add_tag;
rs.add_tag += self.add_tag;
ls.ma += self.add_tag;
rs.ma += self.add_tag;
self.add_tag = 0;
}
void build(int p,int l,int r){
self.l = l;
self.r = r;
self.x1 = xs[l];
self.x2 = xs[r];
self.ma = 0;
self.add_tag =0;
if(l == r){
self.ma = 0;
self.add_tag =0;
return;
}
int mid = (l+r)/2;
build(lp,l,mid);
build(rp,mid+1,r);
push_up(p);
}
void update(int p,int l,int r,int d){
if(l>self.x2 || r < self.x1){
return;
}
if(self.x1>= l && self.x2 <= r){
self.add_tag += d;
self.ma += d;
return;
}
push_down(p);
update(lp,l,r,d);
update(rp,l,r,d);
push_up(p);
}
int query(int p,int l,int r){
if(l>self.r || r < self.l){
return 0;
}
if(self.l>=l && self.r <=r){
return self.ma;
}
push_down(p);
return max(query(lp,l,r),query(rp,l,r));
}
int tot;
bool cmp(lin a,lin b){
return a.y<b.y || (a.y == b.y && a.l>b.l);
}
void solve(){
int n,W,H;
cin>>n>>W>>H;
for(int i= 1;i<=n;i++){
int x,y,l;
cin>>x>>y>>l;
xs[i] = x;
xs[i+n] = x+W-1;
lines[i].x1 = x;
lines[i].x2 = x+W-1;
lines[i].y = y;
lines[i].l = l;
lines[i+n].x1 = x;
lines[i+n].x2 = x+W-1;
lines[i+n].y = y+H-1;
lines[i+n].l = -l;
}
sort(xs+1,xs+1+n);
tot = unique(xs+1,xs+1+n) - xs - 1;
sort(lines+1,lines+1+n,cmp);
build(1,1,tot);
int ans = 0;
for(lin l : lines){
update(1,l.x1,l.x2,l.l);
ans = max(ans,query(1,1,tot));
}
cout<<ans<<'\n';
}
signed main(){
int T;
cin>>T;
while(T--){
solve();
}
}