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

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