题解：P8648 [蓝桥杯 2017 省 A] 油漆面积

zhangmuning1016 · 2025-06-18 20:04:10 · 题解

题目传送门

思路

很明显考虑扫描线。什么是扫描线呢？就是用来算矩形面积并或周长并的方法。具体看 扫描线介绍。

具体做法：

• 把整个矩形并分成若干个小矩形。
• 这些小矩形的 y 坐标就是扫描线扫过的距离，而小矩形的 x 坐标用线段树来维护。

没学过的可以看看 P5490 【模板】扫描线 & 矩形面积并。
注意：要开至少 8 倍空间。

代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=4e5+10;
int n,X[N<<1];
struct node{
    int l,r,h,mk;
    bool operator<(const node&oth)const{
        return h<oth.h;
    }
}li[N<<1];
struct Node{
    int l,r,len,sum;
}hv[N<<2];
inline void fun1(int id){
    if(hv[id].sum)hv[id].len=X[hv[id].r+1]-X[hv[id].l];
    else hv[id].len=hv[(id<<1)].len+hv[(id<<1|1)].len; 
}
void fun2(int id,int l,int r){
    hv[id].l=l,hv[id].r=r;
    hv[id].len=hv[id].sum=0;
    if(l>=r)return;
    int mid=(l+r)>>1;
    fun2((id<<1),l,mid);
    fun2((id<<1|1),mid+1,r);
}
void add(int id,int L,int R,int mrk){
    int l=hv[id].l,r=hv[id].r;
    if(X[l]>=R||X[r+1]<=L)return;
    if(X[l]>=L&&X[r+1]<=R){
        hv[id].sum+=mrk;
        fun1(id);
        return;
    }
    add((id<<1),L,R,mrk);
    add((id<<1|1),L,R,mrk);
    fun1(id);
}
signed main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        int x1_,x2_,y1_,y2_;
        cin>>x1_>>y1_>>x2_>>y2_;
        X[2*i-1]=x1_,X[i<<1]=x2_;
        li[2*i-1]=(node){x1_,x2_,y1_,1};
        li[i<<1]=(node){x1_,x2_,y2_,-1};
    }
    n<<=1;
    sort(X+1,X+n+1);
    sort(li+1,li+n+1);
    int tot=unique(X+1,X+n+1)-X-1;
    fun2(1,1,tot-1);
    int ans=0;
    for(int i=1;i<n;i++){
        add(1,li[i].l,li[i].r,li[i].mk);
        ans+=hv[1].len*(li[i+1].h-li[i].h);
    }
    cout<<ans;
    return 0;
}

时间复杂度是 O(n \log n)，在此题可以接受。