P1502 窗口的星星

• 题目描述
• 分析
• 代码

题目描述

平面上有n个有权点，有一个矩阵能框住最大的和，详情请看题面

分析

首先，我们考虑如何知道两颗星星可以在同一窗户内。
显然，我们可以直接判断，但你发现这做不出来。
我们可以将每个星星对应一个矩阵，若两个矩阵有重叠则这两个星星可以在一个窗口。

这样就可以将问题转换为：平面上有若干个矩形，每个矩形都带有一个权值，求在哪个坐标上权值的总和最大。
然后，跑一遍扫描线就可以了。
注意：小卡买的窗户框是金属做的，所以在边框上的不算在内。所以要减一。

代码

#include<bits/stdc++.h>
#define LL long long
using namespace std;
const int N=1e4+10;
int T,n,w,h;
LL a[N << 1];
struct Tree
{
	int l,r;
	LL maxn,add;
}t[N<<3];
struct node
{
	int x,y,h,l;
	bool operator<(const node &a)const
	{
		return (h!=a.h)?h<a.h:l>a.l;
	}
}p[N<<1];
void build(int p,int l,int r)
{
	t[p].l=l,t[p].r=r,t[p].maxn=t[p].add=0;
	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].maxn+=t[p].add,t[p<<1|1].add+=t[p].add;
	t[p<<1|1].maxn+=t[p].add,t[p<<1].add+=t[p].add;
	t[p].add=0;
}
void add(int p,int x,int y,int k)
{
	int l=t[p].l,r=t[p].r;
	if(x<=l&&r<=y)
	{
		t[p].maxn+=k,t[p].add+=k;
		return ;
	}
	pushdown(p);
	int mid=(l+r)>>1;
	if(x<=mid)add(p<<1,x,y,k);
	if(y>mid)add(p<<1|1,x,y,k);
	t[p].maxn=max(t[p<<1].maxn,t[p<<1|1].maxn);
}
int main()
{
	scanf("%lld",&T);
	while(T--)
	{
		scanf("%d%d%d",&n,&w,&h);
		for(int i=1,x,y,l;i<=n;i++)
		{
			scanf("%d%d%d",&x,&y,&l);
			a[(i<<1)-1]=y,a[(i<<1)]=y+h-1;
			p[(i<<1)-1]=node{y,y+h-1,x,l};
			p[(i<<1)]=node{y,y+h-1,x+w-1,-l};
		}
		n<<=1;
		sort(a+1,a+n+1);
		sort(p+1,p+n+1);
		int cnt=unique(a+1,a+n+1)-a-1;
		for(int i=1;i<=n;i++)
		{
			p[i].x=lower_bound(a+1,a+cnt+1,p[i].x)-a;
			p[i].y=lower_bound(a+1,a+cnt+1,p[i].y)-a;
		}
		build(1,1,cnt);
		LL ans=0;
		for(int i=1;i<=n;i++)
		{
			add(1,p[i].x,p[i].y,p[i].l);
			ans=max(ans,t[1].maxn);
		}
		cout<<ans<<endl;
	}
}