re求调,悬关
查看原帖
re求调,悬关
796667
ZY_jiang楼主2025/1/21 17:17
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ls u<<1
#define rs u<<1|1
const int N=2e4+10;
ll T,n,m,w,h,a[N<<2],cnt,ans;
struct tree{
	ll l,r,maxn,lazy;
}tr[N<<2];
struct node{
	ll l,r,h,val;
}star[N<<2];
bool cmp(node a,node b){
	if(a.h==b.h){
		return a.val>b.val;
	}
	return a.h<b.h;
}
void pushup(ll u){
	tr[u].maxn=max(tr[ls].maxn,tr[rs].maxn);
	return ;
}
void pushdown(ll u){
	if(tr[u].lazy==0) return ;
	tr[ls].maxn+=tr[u].lazy;
	tr[rs].maxn+=tr[u].lazy;
	tr[ls].lazy+=tr[u].lazy;
	tr[rs].lazy+=tr[u].lazy;
	tr[u].lazy=0;
}
void build(ll u,ll l,ll r){
	tr[u].l=l;
	tr[u].r=r;
	tr[u].maxn=tr[u].lazy=0;
	if(l==r){
		return ;
	}
	build(ls,1,(l+r)/2);
	build(rs,(l+r)/2+1,r);
	pushup(u);
	return ;
}
void add(ll u,ll l,ll r,ll k){
	if(l<=tr[u].l&&tr[u].r<=r){
		tr[u].maxn+=k;
		tr[u].lazy+=k;
		return ;
	}
	pushdown(u);
	ll mid=(tr[u].l+tr[u].r)/2;
	if(l<=mid) add(ls,l,r,k);
	if(mid<r) add(rs,l,r,k);
	pushup(u);
	return ;
}
int main(){
	cin>>T;
	while(T--){
		cin>>n>>w>>h;
		memset(a,0,sizeof a);
		memset(tr,0,sizeof tr);
		memset(star,0,sizeof star);
		for(int i=1;i<=n;i++){
			ll x,y,l;
			cin>>x>>y>>l;
			a[i*2-1]=y;
			a[i*2]=y+h-1;
			star[i*2-1].l=y;
			star[i*2-1].r=y+h-1;
			star[i*2-1].h=x;
			star[i*2-1].val=l;
			star[i*2].l=y;
			star[i*2].r=y+h-1;
			star[i*2].h=x+w-1;
			star[i*2].val=-l;
		}
		n<<=1;
		sort(a+1,a+n+1);
		sort(star+1,star+n+1,cmp);
		cnt=unique(a+1,a+n+1)-a-1;
		ans=0;
		build(1,1,cnt-1);
//		cout<<"ok"<<endl;
		for(ll i=1;i<=n;i++){
//			cout<<i<<endl;
			ll l=lower_bound(a+1,a+cnt+1,star[i].l)-a-1;
			ll r=lower_bound(a+1,a+cnt+1,star[i].r)-a-1;
//			cout<<l<<" "<<r<<"\n";
			add(1,l,r,star[i].val);
			ans=max(ans,tr[1].maxn);
		}
		cout<<ans<<'\n';
	}
	return 0;
}
2025/1/21 17:17
加载中...