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

· · 题解

题目传送门：P8648 [蓝桥杯 2017 省 A] 油漆面积

输入为若干矩形，要求输出其覆盖的总面积，即矩形面积并问题，可以用扫描线解决。

扫描线

前置知识：线段树。

我们想象有一条线从下向上扫描。图中四条绿线将图形分割成了三个不重合的矩形，我们可以分别求出其面积。

在知道原矩形每条边的情况下，矩形的高已经有了——拿上边的横坐标减下边。如何求矩形的宽？我们可以用线段树。

我们维护扫描线上每段是否有矩形覆盖，元线段就取离散化后相邻的两个 x 坐标。容易发现，只要元线段的值 \geqslant 1，就要返回这段元线段的长度。

现在的问题是怎么知道一段线段中是否所有的元线段都被覆盖，因为重复贡献同一段是没有用的，但是不计的话删除又会出问题。

这里提供两种方法。

第一种方法：标记永久化。

我们建线段树时记录这段区间真正的的长度 len，然后因为记录的是线段端点，所以如果 l 和 r 在离散化数组中还相隔元素，就继续向下建。注意这里是与维护序列的线段树不同的。

之后的修改中，如果当前区间被大区间包含就将 tag_u 增减 1，否则按正常的线段树向下递归。关键在于 \operatorname{puhsup}：如果 tag_u > 0，则当前区间都被覆盖了，即为 len_u；当非全覆盖时，如果这里是元线段，返回 0，否则要将两条子线段加起来。

void build(int u,int l,int r){
    L[u]=x[l],R[u]=x[r],len[u]=x[r]-x[l];
    if(l<r-1)build(u*2,l,(l+r)/2),build(u*2+1,(l+r)/2,r);
}
void update(int u,int l,int r,short p){
    if(l<=L[u]&&R[u]<=r)tag[u]+=p;
    else if(l<=R[u]&&L[u]<=r)update(u*2,l,r,p),update(u*2+1,l,r,p);
    if(tag[u]>0)s[u]=len[u];
    else s[u]=s[u*2]+s[u*2+1];// 不要学习这种写法，会让你需要多一倍的空间
}

第二种方法：我们用普通的线段树，发现维护区间被覆盖数的最小值和被覆盖最少处的长度即可。若前者为 0 则从 len 中减去后者，这两个信息都具有可合并性。

代码实现

我们采取第一种方法，先离散化再建线段树，按照纵坐标升序遍历所有边即可。

#include<iostream>
#include<algorithm>
using namespace std;
const int N=20004;
int n,tot,x[N],L[N<<8],R[N<<8],len[N<<8];
struct line{
    int xl,xr,y;
    short p;
}a[N];
bool cmp(line a,line b){
    return a.y<b.y;
}
long long s[N<<8],tag[N<<8],ans;
void build(int u,int l,int r){
    L[u]=x[l],R[u]=x[r],len[u]=x[r]-x[l];
    if(l<r-1)build(u<<1,l,(l+r>>1)),build(u<<1|1,(l+r>>1),r);
}
void update(int u,int l,int r,short p){
    if(!len[u])return;
    if(l<=L[u]&&R[u]<=r)tag[u]+=p;
    else if(l<=R[u]&&L[u]<=r)update(u<<1,l,r,p),update(u<<1|1,l,r,p);
    s[u]=(tag[u]>0?len[u]:s[u<<1]+s[u<<1|1]);
}
int main(){
    cin>>n;
    for(int i=1,x1,y1,x2,y2;i<=n;i++){
        cin>>x1>>y1>>x2>>y2;
        if(x1>x2)swap(x1,x2);
        if(y1>y2)swap(y1,y2);
        x[(i<<1)-1]=x1,x[i<<1]=x2;
        a[(i<<1)-1]={x1,x2,y1,1},a[i<<1]={x1,x2,y2,-1};
    }
    n<<=1;
    sort(x+1,x+1+n);
    sort(a+1,a+1+n,cmp);
    tot=unique(x+1,x+1+n)-x-1;
    build(1,1,tot);
    for(int i=1;i<=n;i++){
        if(a[i].y!=a[i-1].y)ans+=s[1]*(a[i].y-a[i-1].y);
        update(1,a[i].xl,a[i].xr,a[i].p);
    }
    cout<<ans;
    return 0;
}

AC 记录。