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

· · 题解

Description

由于题意中的矩形的长宽固定，故只要固定矩形的右下方的端点，即可确定一个矩形。
我们可以用矩形的右下端点来代表一个矩形。

以上图片的红点为右下端点。
我们定义一个矩形的右下端点为 P 点。

现在我们考虑一个点 A 可以对那些 P 点产生贡献。
很显然，在以 A 为左上端点，长为 W，宽为 H 的矩形内的所有 P 点，都可以吃到 A 的贡献。如下图：

所以我们可以确定坐标，如下图：

现在问题转化为：
给你 n 个矩形，每个矩形有一个权值，一个点的权值为所有覆盖这个点的矩形的权值之和，求所有点权值的最大值。

Solution

我们可以使用扫描线解决。

先离散化矩形的端点。

for(int i = 1;i<=n;++i){
  int x1 = read<int>(),y1 = read<int>();
  int val = read<int>();
  int x2 = x1+W-1,y2 = y1-H+1;
  a[i] = (Rectangle){x1,y1,x2,y2,val};
  tmpX[++lenX] = x1,tmpX[++lenX] = x2;
  tmpY[++lenY] = y1,tmpY[++lenY] = y2;
} 
std::sort(tmpX+1,tmpX+lenX+1);
std::sort(tmpY+1,tmpY+lenY+1);
lenX = std::unique(tmpX+1,tmpX+lenX+1)-tmpX-1;
lenY = std::unique(tmpY+1,tmpY+lenY+1)-tmpY-1;
for(int i = 1;i<=n;++i){
  a[i].x1 = std::lower_bound(tmpX+1,tmpX+lenX+1,a[i].x1)-tmpX;
  a[i].x2 = std::lower_bound(tmpX+1,tmpX+lenX+1,a[i].x2)-tmpX;
  a[i].y1 = std::lower_bound(tmpY+1,tmpY+lenY+1,a[i].y1)-tmpY;
  a[i].y2 = std::lower_bound(tmpY+1,tmpY+lenY+1,a[i].y2)-tmpY;
}

我们考虑怎样添加一个矩形。

暴力：

for(int i = x1;i<=x2;++i)
    Plus(y2,y1,val);//[y2,y1]区间加

考虑差分：

Plus(y2,y1,val)//i = x1
Plus(y2,y1,-val)//i = x2+1

现在添加一个矩形只需两次区间加操作，用线段树即可。

完整代码：

#include<cstdio>
#include<algorithm>
#include<vector>
#define ll long long
const int N = 1e5+5;
inline ll max(ll a,ll b){return a>b?a:b;}
struct Segment_Tree{
    struct Tree{
        int lson,rson;
        ll Max,Add; 
        inline void Fun_Add(ll val){
            Max += val,
            Add += val;
        }
    }tree[N<<2];
    int root,total;
    inline void build(int &rt,int l,int r){
        rt = ++total;
        if(l == r) return ;
        int mid = l+r>>1;
        build(tree[rt].lson,l,mid);
        build(tree[rt].rson,mid+1,r); 
    }
    inline void push_up(int rt){
        tree[rt].Max = max(tree[tree[rt].lson].Max,tree[tree[rt].rson].Max);
    }
    inline void push_down(int rt){
        if(tree[rt].Add)
            tree[tree[rt].lson].Fun_Add(tree[rt].Add),
            tree[tree[rt].rson].Fun_Add(tree[rt].Add),
            tree[rt].Add = 0;
    }
    inline void Plus(int rt,int treeL,int treeR,int askL,int askR,ll val){
        if(askL <= treeL && treeR <= askR)
            return tree[rt].Fun_Add(val);
        push_down(rt);
        int mid = treeL+treeR>>1;
        if(askL<=mid) Plus(tree[rt].lson,treeL,mid,askL,askR,val);
        if(askR>mid) Plus(tree[rt].rson,mid+1,treeR,askL,askR,val);
        push_up(rt);
    }
}T;
struct Rectangle{
    int x1,y1,x2,y2,val;
}a[N];
struct Node{
    int l,r,val;
};
std::vector<Node> Key[N<<1];
int tmpX[N<<1],tmpY[N<<1];
int main(){
    int n,W,H;
    std::scanf("%d %d %d",&n,&W,&H);
    int lenX = 0,lenY = 0;
    for(int i = 1;i<=n;++i){
        int x1,y1,val;
        std::scanf("%d %d %d",&x1,&y1,&val);
        int x2 = x1+W-1,y2 = y1-H+1;
        a[i] = (Rectangle){x1,y1,x2,y2,val};
        tmpX[++lenX] = x1,tmpX[++lenX] = x2;
        tmpY[++lenY] = y1,tmpY[++lenY] = y2;
    } 
    std::sort(tmpX+1,tmpX+lenX+1);
    std::sort(tmpY+1,tmpY+lenY+1);
    lenX = std::unique(tmpX+1,tmpX+lenX+1)-tmpX-1;
    lenY = std::unique(tmpY+1,tmpY+lenY+1)-tmpY-1;
    for(int i = 1;i<=n;++i){
        a[i].x1 = std::lower_bound(tmpX+1,tmpX+lenX+1,a[i].x1)-tmpX;
        a[i].x2 = std::lower_bound(tmpX+1,tmpX+lenX+1,a[i].x2)-tmpX;
        a[i].y1 = std::lower_bound(tmpY+1,tmpY+lenY+1,a[i].y1)-tmpY;
        a[i].y2 = std::lower_bound(tmpY+1,tmpY+lenY+1,a[i].y2)-tmpY;
    }
    for(int i = 1;i<=n;++i){
        int l = a[i].y2,r = a[i].y1;
        Key[a[i].x1].push_back({l,r,a[i].val});
        Key[a[i].x2+1].push_back({l,r,-a[i].val});
    }
    T.build(T.root,1,lenY);
    ll ans = 0;
    for(int i = 1;i<=lenX;++i){
        for(Node v : Key[i]) T.Plus(T.root,1,lenY,v.l,v.r,v.val);
        ans = max(ans,T.tree[T.root].Max);
    }
    std::printf("%lld",ans);
    return 0;
}

时间复杂度：O(n \log n)。

PS：真不知道题目的双指针标签是干嘛的。