扫描线应该打懒标记的……
#include <algorithm>
#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
int T, n, m, w, h, cnt, uu, vv, ww, zdz[80005], ans, tag[80005];
ll num[20005];
struct Line{
ll xx, yu, yv, fla;
}li[20005];
bool cmp(Line x, Line y){
if(x.xx!=y.xx) return x.xx<y.xx;
else return x.fla<y.fla;
}
void build(int o, int l, int r){
tag[o] = 0;
if(l+1==r) zdz[o] = 0;
else{
int mid=(l+r)>>1;
int lson=o<<1;
int rson=lson|1;
if(l<=mid) build(lson, l, mid);
if(mid<=r) build(rson, mid, r);
zdz[o] = 0;
}
}
void pushDown(int o, int l, int r, int lson, int rson){
zdz[lson] += tag[o];
zdz[rson] += tag[o];
tag[lson] += tag[o];
tag[rson] += tag[o];
tag[o] = 0;
}
void update(int o, int l, int r, const Line &x){
if(num[l]>=x.yu && num[r]<=x.yv) zdz[o] += x.fla, tag[o] += x.fla;
else{
int mid=(l+r)>>1;
int lson=o<<1;
int rson=lson|1;
if(tag[o]) pushDown(o, l, r, lson, rson);
if(x.yu<num[mid]) update(lson, l, mid, x);
if(x.yv>num[mid]) update(rson, mid, r, x);
zdz[o] = max(zdz[lson], zdz[rson]);
}
}
int main(){
cin>>T;
while(T--){
scanf("%d %d %d", &n, &w, &h);
cnt = 0;
for(int i=1; i<=n; i++){
scanf("%d %d %d", &uu, &vv, &ww);
num[++cnt] = vv;
li[cnt] = (Line){uu, vv, (ll)vv+h, ww};
num[++cnt] = (ll)vv + h;
li[cnt] = (Line){(ll)uu+w, vv, (ll)vv+h, -ww};
}
sort(li+1, li+1+cnt, cmp);
sort(num+1, num+1+cnt);
m = unique(num+1, num+1+cnt) - num - 1;
build(1, 1, m);
ans = 0;
for(int i=1; i<=cnt; i++){
ans = max(ans, zdz[1]);
update(1, 1, m, li[i]);
}
printf("%d
", ans);
}
return 0;
}