题解：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

#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);
}