题解：P1502 窗口的星星

题意简述

给定平面上

n

个点，求一个

w \times h

的矩形最多覆盖多少点权（边长平行于坐标轴，矩形不含边框，给出的是坐标系坐标）

n \le 10^4

思路

考虑一颗星星何时会产生贡献，即出现在矩形中，显然

x

坐标符合条件的矩形一定以其为右端点的一段区间，换句话说，只要窗户的右上角出现在一颗星星的右上角的一段区间里，这颗星星就会被覆盖，产生贡献。

考虑对于一颗星星

(x,y)

区间范围为

(x,y) \sim(x+w,y+h)

，由于不算边框，故减去

1

为

(x,y) \sim(x+w-1,y+h-1)

。而所有星星的区间会重合，只需要找到权最大的区间即可。

这样的问题可以直接用扫描线和线段树高效处理，对于一颗星星的区间加入就加上亮度值，退出就减掉，每次打擂台最后留下的就是最大值。

注意

由于我们只关心全局最大，所以线段树不需要 query 操作。
坐标非常大，所以采用离散化与 long long。

code:

CPP

#include<bits/stdc++.h>
#define lid id<<1
#define rid id<<1|1
using namespace std;
const int maxn=100005;
long long t,n,w,h;
long long a[maxn<<1];//记得开long long 

struct node{
	long long l,r,sum;
	long long lazy;
}tr[maxn<<2];
struct STU{
	long long l,r,h,val;
	bool operator <(const STU&x)const{
		return (h!=x.h)?h<x.h:val>x.val;
	}//这段其实等价于cmp，后来去题解里学了一下重载运算符 
}line[maxn<<2];

void pushup(long long id){
	tr[id].sum=max(tr[lid].sum,tr[rid].sum);
}
void pushdown(long long id){
	if(tr[id].lazy){
		tr[lid].sum+=tr[id].lazy;
		tr[rid].sum+=tr[id].lazy;
		tr[lid].lazy+=tr[id].lazy;
		tr[rid].lazy+=tr[id].lazy;
		tr[id].lazy=0;
	}
}

void build(long long id,long long l,long long r){
	tr[id].l=l,tr[id].r=r;
	tr[id].sum=tr[id].lazy=0;
	if(l==r) return;
	long long mid=(l+r)/2;
	build(lid,l,mid);
	build(rid,mid+1,r);
	//这里扫描线时才加值，所以初始化为0即可 
}

void modify(long long id,long long l,long long r,long long v){
	if(tr[id].l>=l&&tr[id].r<=r){
		tr[id].lazy+=v;
		tr[id].sum+=v;
		return;
	}
	pushdown(id);
	long long mid=(tr[id].l+tr[id].r)/2;
	if(l<=mid) modify(lid,l,r,v);
	if(r>mid) modify(rid,l,r,v);
	pushup(id);
}
int main(){
	cin>>t;
	for(int q=1;q<=t;q++){
		cin>>n>>w>>h;
		memset(tr,0,sizeof(tr));
		memset(line,0,sizeof(line));
		memset(a,0,sizeof(a));
		for(long long i=1;i<=n;i++){
			long long x,y,l;
			cin>>x>>y>>l;
			a[i<<1-1]=y;
			a[i<<1]=y+h-1;
			line[i<<1-1].l=y;
			line[i<<1-1].r=y+h-1;
			line[i<<1-1].h=x;
			line[i<<1-1].val=l;
			line[i<<1].l=y;
			line[i<<1].r=y+h-1;line[i<<1].h=x+w-1;
			line[i<<1].val=-l; //每个星星的信息 
		}
		n*=2;
		sort(a+1,a+n+1);
		sort(line+1,line+n+1);
		long long num=unique(a+1,a+n+1)-a-1;//离散化 
		long long ans=0;
		build(1,1,num-1);
		for (long long i=1;i<=n;i++){
		    long long l=lower_bound(a+1,a+num+1,line[i].l)-a-1;
			long long r=lower_bound(a+1,a+num+1,line[i].r)-a-1;
			modify(1,l,r,line[i].val);
			ans=max(ans,tr[1].sum);
		}
		cout<<ans<<endl;
	}
	return 0;
}

题解：P1502 窗口的星星

文章操作

题意简述

思路

注意

code:

相关推荐

评论

题解：P1502 窗口的星星