P8370 [POI 2001] Goldmine 题解

比较简单的扫描线题。

前置芝士

扫描线、线段树~~、离散化（？）~~。

题目大意

给定平面上的

n

个点坐标

(x_i, y_i)

和矩形尺寸

s \times w

，求该矩形能覆盖点数的最大值。矩形边平行于坐标轴，点在矩形边上也算被覆盖。

算法思路

扫描线算法

将每个点视为一个矩形区域的起点和终点，转化为事件处理：每个矿石

(x, y)

生成两个事件：

左事件：当矩形左边界到达 $x-s$ 时，覆盖区间 $[y-w, y]$ 。
右事件：当矩形右边界到达 $x$ 时，移除该区间。

示意图

CPP

矿石点(x, y) → 影响区间[x-s, x] × [y-w, y]
       ↑右事件          ↑左事件

由于数据规模较大，我们还要使用线段树加速以及离散化节约空间（其实可以不用，但是精益求精嘛，这就是为什么有点提交记录用了 10MB 空间而有点只用了 4MB ）。

要注意的点：

一个点对应两个事件，一个事件对应两个 y 坐标，线段树本身要开 $4$ 倍空间，所以 tree 数组要开到 $n_{max} \times 16$ 。
先处理左事件（先加再减）防止提前减少覆盖数（如果边界上的点不算就要先减再加）。所以可以按照 x 坐标排序。

code

CPP

#include<bits/stdc++.h>
#ifdef _WIN32
#define gc(c) getchar(c)
#else
#define gc(c) getchar_unlocked(c)
#endif
#define isd(c) (c>='0'&&c<='9')
#define For(i,a,b) for(auto i=(a);i<=(b);i++)
#define ls (node<<1)
#define rs (node<<1|1)
using namespace std;

namespace temp{
template<class T>void read(T &n){
    n=0;char c=gc();int k=1;
    while(!isd(c)){if(c=='-')k*=-1;c=gc();}
    while(isd(c))n=n*10+c-'0',c=gc();
    n*=k;
}
template<class T>void write(T n){
    if(n<0)n=-n,putchar('-');
    if(n>9)write(n/10);
    putchar(n%10+'0');
}
}

namespace Main{
using namespace temp;

const int MAXN=15005;

struct event {
    int x, type;// 事件发生x坐标 事件类型(0:添加区域,1:移除区域)
    int y_low, y_high;//原始y轴下界y-w 原始y轴上界y
    int dl, dr;  //离散化后的上下界索引
    
    bool operator<(const event&oth){
        return x != oth.x ? x < oth.x : type < oth.type;
    }//按 x 坐标排序
};

event evt[MAXN<<1];// 事件数组（每个矿石生成两个事件）
int ys[MAXN<<2], tot;// 离散化坐标数组及计数器

struct sgt {
    int l,r;    
    int add,maxv;
} tree[MAXN<<4]; // 2个事件*2个y坐标*4倍空间线段树

void push_down(int node) {
    if (tree[node].add && tree[node].l < tree[node].r) {
        tree[ls].add+=tree[node].add;
        tree[ls].maxv+=tree[node].add;
        tree[rs].add+=tree[node].add;
        tree[rs].maxv+=tree[node].add;
        
        tree[node].add=0;
    }
}

void build(int node,int l,int r) {
    tree[node].l=l;
    tree[node].r=r;
    tree[node].add=tree[node].maxv=0;
    if (l==r) return;
    
    int mid=(l+r)>>1;
    build(ls,l,mid);
    build(rs,mid+1,r);
}

void update(int node,int l,int r,int val){
    if(r<tree[node].l||l>tree[node].r)return;
    if(l<=tree[node].l&&tree[node].r<=r){
        tree[node].add+=val;
        tree[node].maxv+=val;
        return;
    }
    
    push_down(node);
    update(ls,l,r,val);
    update(rs,l,r,val);
    tree[node].maxv=max(tree[ls].maxv,tree[rs].maxv)+tree[node].add;
}

int s,w,n,x,y;
int cnt,ans;
void Main(){
    read(s),read(w),read(n);
    
    For(i,1,n) {
        read(x),read(y);
        evt[cnt++]={x-s,0,y-w,y};
        // 生成左事件（矩形进入）：x-s坐标，类型0
        evt[cnt++]={x,1,y-w,y};
        // 生成右事件（矩形离开）：x坐标，类型1
        ys[tot++]=y-w;
        ys[tot++]=y;
        // 离散化
    }
    
    sort(ys, ys+tot);
    tot=unique(ys, ys+tot)-ys;// 去重
    
    // 离散化
    For(i,0,cnt-1)
        evt[i].dl=lower_bound(ys, ys+tot,evt[i].y_low)-ys,    // 下界对应索引
        evt[i].dr=upper_bound(ys, ys+tot,evt[i].y_high)-ys -1;// 上界对应索引
    
    sort(evt,evt+cnt);
    build(1,0,tot-1);
    
    For(i,0,cnt-1) {
        if(evt[i].dl>evt[i].dr) continue;
        update(1, evt[i].dl,evt[i].dr,evt[i].type ? -1 : 1);
        ans = max(ans, tree[1].maxv);
    }
    write(ans);
}
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    Main::Main();
    return 0;
}

时间复杂度

O(n \log n)

(实际上主要是排序和离散化的时间复杂度)可以通过此题。

record

题解：P8370 [POI 2001] Goldmine

文章操作