题解：P12119 [NordicOI 2025] 垃圾收集 / Garbage Collection

思路

我们考虑将垃圾按

x

排序，然后维护一个集合，使这个集合中的最大的横坐标之差不大于

W

。

这个集合的维护是简单的，从左往右扫，每次遇到一个新的垃圾就去集合末尾踢掉一些垃圾。由于每个垃圾最多只会被加进集合一次，踢出集合一次，所以复杂度十分的正确。

那么接下来考虑如何快速计算集合内的答案。

我们考虑记

l_i

表示我们能选择的矩形的靠下的那条边纵坐标为

i

时，能捞到的垃圾重量之和。

下一步考虑加入一个新的垃圾进入集合，会对哪些

l_i

产生影响。

这个很容易就能推出来，当加入了一个纵坐标为

y_i

的新垃圾，那么当你的矩形最下面一条边的纵坐标

i

满足

y_i-H+1\leq i \leq y_i

时，你就可以捞到这个垃圾。

发现这是一个十分简单的区间修改，搞个线段树，发现这个纵坐标有点大，搞个离散化。

code

CPP

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n,w,h;
const int N=1e5+5;
struct point
{
	int x,y,w;
	int ly,hy;
}a[N];
int b[N<<1];
int tot;
inline bool operator<(point a,point b)
{
	return a.x^b.x?a.x<b.x:a.y^b.y?a.y<b.y:a.w<b.w;
}
struct sgt
{
	int lar[N<<2],add[N<<2];
#define lx (x<<1)
#define rx (x<<1|1)
#define mid (L+R>>1)
	inline void up(int x)
	{
		lar[x]=max(lar[lx],lar[rx]);
		return;
	}
	inline void tag(int x,int L,int R)
	{
		if(add[x])
		{
			lar[lx]+=add[x];
			lar[rx]+=add[x];
			add[lx]+=add[x];
			add[rx]+=add[x];
			add[x]=0;
		}
		return;
	}
	void update(int x,int L,int R,int l,int r,int v)
	{
		if(l<=L&&R<=r){lar[x]+=v,add[x]+=v;return;}
		tag(x,L,R);
		if(l<=mid)update(lx,L,mid,l,r,v);
		if(r>mid)update(rx,mid+1,R,l,r,v);
		up(x);
		return;
	}
}subaru;
int ans;
signed main()
{
	ios::sync_with_stdio(false),cin.tie(nullptr),cout.tie(nullptr);
	cin>>n>>w>>h;
	for(int i=1;i<=n;++i)cin>>a[i].x>>a[i].y>>a[i].w,b[++tot]=a[i].y,b[++tot]=a[i].y-h+1;
	sort(a+1,a+1+n);
	sort(b+1,b+1+tot);
	tot=unique(b+1,b+1+tot)-b-1;
	for(int i=1;i<=n;++i)a[i].ly=lower_bound(b+1,b+1+tot,a[i].y-h+1)-b,a[i].hy=lower_bound(b+1,b+1+tot,a[i].y)-b;
	for(int i=1,j=1;i<=n;++i)
	{
		subaru.update(1,1,n,a[i].ly,a[i].hy,a[i].w);
		while(a[j].x+w-1<a[i].x)subaru.update(1,1,n,a[j].ly,a[j].hy,-a[j].w),++j;
		ans=max(ans,subaru.lar[1]);
	}
	cout<<ans;
	return 0;
}

题解：P12119 [NordicOI 2025] 垃圾收集 / Garbage Collection

文章操作

思路

code

相关推荐

评论

题解：P12119 [NordicOI 2025] 垃圾收集 / Garbage Collection