40pts求调 扫描线
查看原帖
40pts求调 扫描线
766436
Mr_RedStone楼主2025/6/14 20:45
#include<bits/stdc++.h>
using namespace std;
int T;
int n,w,h;
const int NR=1e5+5;
struct Line{
	long long y,x1,x2;
	long long op;
	friend bool operator <(Line a,Line b){
		if(a.y!=b.y) return a.y<b.y;
		return a.op<b.op;
	}
}a[2*NR];
long long b[2*NR];
struct Node{
	int l,r;
	long long mx=0,add=0;
	friend Node operator +(const Node& a,const Node& b){
		Node c;
		c.l=min(a.l,b.l);
		c.r=max(a.r,b.r);
		c.mx=max(a.mx,b.mx);
		return c;
	}
}tr[8*NR];
void pushdown(int x){
	int l=x<<1,r=(x<<1)+1;
	tr[l].add+=tr[x].add;
	tr[l].mx+=tr[x].add;
	tr[r].add+=tr[x].add;
	tr[r].mx+=tr[x].add;
	tr[x].add=0;
}
void build(int x,int l,int r){
	if(l==r){
		tr[x]={l,r,0,0};
		return;
	}
	int mid=(l+r)>>1;
	build(x<<1,l,mid);
	build((x<<1)+1,mid+1,r);
	tr[x]=tr[x<<1]+tr[(x<<1)+1];
}
void add(int x,int l,int r,long long k){
	if(r<tr[x].l||l>tr[x].r) return;
	if(l<=tr[x].l&&tr[x].r<=r){
		tr[x].add+=k;
		tr[x].mx+=k;
		return;
	}
	pushdown(x);
	add(x<<1,l,r,k);
	add((x<<1)+1,l,r,k);
	tr[x]=tr[x<<1]+tr[(x<<1)+1];
}
int main(){
	scanf("%d",&T);
	while(T--){
		memset(tr,0,sizeof(tr));
		memset(a,0,sizeof(a));
		memset(b,0,sizeof(b));
		scanf("%d %d %d",&n,&w,&h);
		for(int i=1;i<=n;i++){
			long long x1,y1;
			long long v;
			scanf("%lld %lld %lld",&x1,&y1,&v);
			long long x2=x1+w-1,y2=y1+h-1;
			a[i]={x1,y1,y2,v};
			a[i+n]={x2,y1,y2,-v};
			b[i]=x1,b[i+n]=x2;
		}
		sort(a+1,a+2*n+1);
		sort(b+1,b+2*n+1);
		int sz=unique(b+1,b+2*n+1)-b-1;
		build(1,1,sz);
		long long ans=0;
		for(int i=1;i<=2*n;i++){
			int p1=lower_bound(b+1,b+sz+1,a[i].x1)-b;
			int p2=lower_bound(b+1,b+sz+1,a[i].x2)-b;
			add(1,p1,p2,a[i].op);
			ans=max(ans,tr[1].mx);
		}
		printf("%lld\n",ans);
	}
	return 0;
}
2025/6/14 20:45
加载中...