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

可以发现，如果只考虑长度为

W

是很简单的，只需要使用双指针维护，如果当前垃圾的横坐标与所维护的左端点垃圾的横坐标差值大于

W

则弹出左端点，直到符合条件为止，也就是说我们可以使用很优的时间复杂度来遍历所有长度为

W

的区间，接下来只需要考虑如何快速求出每个长度合法的区间的答案即可。如果直接扫描难以解决，所以我们换个思路，用

t_y

表示当这个矩形下面的边的纵坐标为

y

时的答案。最终答案即为

t_i

的最大值，我们考虑当加入或者删除一个点时对

t_i

的影响，显然加入点

i

时对于区间

[y_i-h+1,y_i]

的

t

值会增加

w_i

，删除时则减少，这就是一个区间修改，线段树维护即可，由于值域较大，需要离散化。

AC code

CPP

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=2e5+5;
int n,w,h,t[N<<2],b[N],tag[N],cnt;
struct tub{int x,y,w;}a[N];
void push_up(int p){t[p]=max(t[p<<1],t[p<<1|1]);}
void addtag(int p,int d){
	t[p]+=d;
	tag[p]+=d;
}
void push_down(int p){
	if(tag[p]){
		addtag(p<<1,tag[p]);
		addtag(p<<1|1,tag[p]);
		tag[p]=0;
	}
}
void update(int p,int l,int r,int L,int R,int d){
	if(L<=l&&R>=r){
		addtag(p,d);
		return;
	}
	int mid=(l+r)>>1;
	push_down(p);
	if(L<=mid) update(p<<1,l,mid,L,R,d);
	if(R>mid) update(p<<1|1,mid+1,r,L,R,d);
	push_up(p);
}
bool cmp(tub x,tub y){return x.x<y.x;}
signed main(){
	scanf("%lld%lld%lld",&n,&w,&h);
	for(int i = 1;i<=n;i++){
		scanf("%lld%lld%lld",&a[i].x,&a[i].y,&a[i].w);
		b[++cnt]=a[i].y; b[++cnt]=a[i].y-h+1;
	}
	sort(a+1,a+1+n,cmp); sort(b+1,b+1+cnt);
	int m = unique(b+1,b+1+cnt)-b-1; int j=1,ans=0;
	for(int i = 1;i<=n;i++){
		int ly=lower_bound(b+1,b+1+m,a[i].y-h+1)-b;
		int ry=lower_bound(b+1,b+1+m,a[i].y)-b; 
		update(1,1,2e5,ly,ry,a[i].w);
		while(a[j].x+w-1<a[i].x){
			ly=lower_bound(b+1,b+1+m,a[j].y-h+1)-b;
			ry=lower_bound(b+1,b+1+m,a[j].y)-b;
			update(1,1,2e5,ly,ry,-a[j].w);
			j++;
		}
		ans=max(ans,t[1]);
	}
	printf("%lld",ans);
}

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

文章操作

AC code

相关推荐

评论

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