# 求助。关于线段树的区间

@春风  2020-09-24 22:04 回复

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=1e4+10;
int n,T;
ll W,H,X[MAXN],ans;
struct Segt{
int l,r;
ll sum,jud;
}t[MAXN<<3];
struct Seg{
ll l,r,h,w;
bool operator < (const Seg &b)const{
if(h==b.h) return w>b.w;
return h<b.h;
}
}line[MAXN<<1];
ll Max(ll x,ll y) { return x>y?x:y; }
void Build(int p,int l,int r){
t[p].l=l; t[p].r=r;
if(l==r) return;
int mid=(l+r)>>1;
Build(p<<1,l,mid);
Build(p<<1|1,mid+1,r);
}
void Pushdown(int p){
t[p<<1].jud+=t[p].jud;
t[p<<1|1].jud+=t[p].jud;
t[p<<1].sum+=t[p].jud;
t[p<<1|1].sum+=t[p].jud;
t[p].jud=0;
}
void Leadin(int p,int pl,int pr,ll we){
int l=t[p].l,r=t[p].r;
// printf("%d %d %d %d\n",l,r,pl,pr);
if(pl>=r+1||pr<=l) return;
if(pl<=l&&pr>=r+1){
t[p].jud+=we;
t[p].sum+=we;
return;
}
Pushdown(p);
t[p].sum=Max(t[p<<1].sum,t[p<<1|1].sum);
}
signed main(){
scanf("%d",&T);
while(T--){
scanf("%d%lld%lld",&n,&W,&H);
ans=0;
memset(t,0,sizeof t);
for(int i=1;i<=n;++i){
ll x,y,light;
scanf("%lld%lld%lld",&x,&y,&light);
line[2*i-1]=(Seg){x,x+W-1,y,light};
line[2*i]=(Seg){x,x+W-1,y+H-1,-light};
X[2*i-1]=x;
X[2*i]=x+W-1;
}
n<<=1;
sort(X+1,X+1+n);
sort(line+1,line+1+n);
int tot=unique(X+1,X+1+n)-X-1;
Build(1,1,tot-1);
// for(int i=1;i<=n;++i) printf("line[%d]=%lld %lld %lld %lld\n",i,line[i].l,line[i].r,line[i].h,line[i].w);
for(int i=1;i<=n;++i){
int pl=lower_bound(X+1,X+1+tot,line[i].l)-X;
int pr=lower_bound(X+1,X+1+tot,line[i].r)-X;
printf("line=%d %d %lld %lld\n",pl,pr,line[i].l,line[i].r);
printf("sum%d=%lld\n",i,t[1].sum);
ans=Max(ans,t[1].sum);
}
printf("%lld\n",ans);
}
return 0;
}

#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int MAXN=1e4+10;
int n,T;
ll W,H,X[MAXN<<1],ans;
struct Segt{
int l,r;
ll sum,jud;
}t[MAXN<<3];
struct Seg{
ll l,r,h,w;
bool operator < (const Seg &b)const{
if(h==b.h) return w>b.w;
return h<b.h;
}
}line[MAXN<<2];
ll Max(ll x,ll y) { return x>y?x:y; }
void Build(int p,int l,int r){
t[p].l=l; t[p].r=r;
if(l==r) return;
int mid=(l+r)>>1;
Build(p<<1,l,mid);
Build(p<<1|1,mid+1,r);
}
void Pushdown(int p){
t[p<<1].jud+=t[p].jud;
t[p<<1|1].jud+=t[p].jud;
t[p<<1].sum+=t[p].jud;
t[p<<1|1].sum+=t[p].jud;
t[p].jud=0;
}
void Leadin(int p,int pl,int pr,ll we){
int l=t[p].l,r=t[p].r;
// printf("%d %d %d %d\n",l,r,pl,pr);
// if(pl>r||pr<l) return;
if(pl<=l&&pr>=r){
t[p].jud+=we;
t[p].sum+=we;
return;
}
int mid=(l+r)>>1;
Pushdown(p);
t[p].sum=Max(t[p<<1].sum,t[p<<1|1].sum);
}
signed main(){
scanf("%lld",&T);
while(T--){
scanf("%d%lld%lld",&n,&W,&H);
ans=0;
memset(t,0,sizeof t);
memset(line,0,sizeof line);
for(int i=1;i<=n;++i){
ll x,y,light;
scanf("%lld%lld%lld",&x,&y,&light);
line[2*i-1]=(Seg){x,x+W-1,y,light};
line[2*i]=(Seg){x,x+W-1,y+H-1,-light};
X[2*i-1]=x;
X[2*i]=x+W-1;
}
n<<=1;
sort(X+1,X+1+n);
sort(line+1,line+1+n);
int tot=unique(X+1,X+1+n)-X-1;
Build(1,1,tot-1);
// for(int i=1;i<=n;++i) printf("line[%d]=%lld %lld %lld %lld\n",i,line[i].l,line[i].r,line[i].h,line[i].w);
for(int i=1;i<n;++i){
int pl=lower_bound(X+1,X+1+tot,line[i].l)-X-1;
int pr=lower_bound(X+1,X+1+tot,line[i].r)-X-1;
// printf("line=%d %d %lld %lld\n",pl,pr,line[i].l,line[i].r);
// printf("sum%d=%lld\n",i,t[1].sum);
ans=Max(ans,t[1].sum);
}
printf("%lld\n",ans);
}
return 0;
}