题解：P8734 [蓝桥杯 2020 国 A] 奇偶覆盖

· · 题解

昨天刚学会扫描线，赶紧来写一篇题解

前置知识：扫描线

还不会扫描线的看这题，本题解不再讲述扫描线的实现。

题意

给出 n 个矩形，求被奇数次和被偶数次覆盖的面积。

思路

这题就是扫描线模板稍微改一改

和模板题不一样，这题需要维护两个区间长度（奇数次覆盖和偶数次覆盖）。

看到很多题解都这么做了，维护 len1 和 len2 ，pushup 函数感觉好麻烦

我很懒，所以不想改动板子，所以想出来一个相对简单一些的做法：

模板里的总长度 len 不要扔掉，只需维护奇数次覆盖长度 len1 ，偶数次长度只需 len - len1 即可。

现在考虑如何维护奇数次覆盖长度 len1 。

分三种情况：

1.区间没被覆盖：左右儿子相加即可。

2.区间覆盖次数为奇数：奇 + 奇 = 偶，如果左右儿子有覆盖次数为奇数的，相加即为偶数，需要去掉。所以奇数次覆盖长度 = 区间总长 - 左右儿子奇数次覆盖长度。

3.区间覆盖次数为偶数：偶 + 奇 = 奇，还是左右儿子相加

上述所有操作在 pushup 函数内实现：

void push_up(int p){
  //模板 
    if(T[p].cover)T[p].len=xx[T[p].r]-xx[T[p].l];
    else T[p].len=T[lch].len+T[rch].len;
  //奇数次覆盖长度
    if(T[p].cover&1)T[p].len1=xx[T[p].r]-xx[T[p].l]-(T[lch].len1+T[rch].len1);//第二种情况
    else T[p].len1=T[lch].len1+T[rch].len1;//第一种情况和第三种情况
}

完整代码：

拒绝抄袭代码，共创和谐洛谷

#include<iostream>
#include<algorithm>
#define int long long
#define lch (p<<1)
#define rch (p<<1|1)
using namespace std;
const int N=1e5+10;
struct node{
    int l,r,len,len1,cover;
}T[N<<4];//空间开大些保险
struct Line{
    int lx,rx,y,inout;
    friend bool operator < (const Line &x,const Line &y){
        return x.y<y.y;
    }
}line[N<<1];
int n,m,xx[N<<1],ans,nx,ny,cnt,k,ans1;
char op;
void push_up(int p){
  //模板 
    if(T[p].cover)T[p].len=xx[T[p].r]-xx[T[p].l];
    else T[p].len=T[lch].len+T[rch].len;
  //奇数次覆盖长度
    if(T[p].cover&1)T[p].len1=xx[T[p].r]-xx[T[p].l]-(T[lch].len1+T[rch].len1);//第二种情况
    else T[p].len1=T[lch].len1+T[rch].len1;//第一种情况和第三种情况
}
void build(int p,int l,int r){
    T[p].l=l,T[p].r=r,T[p].len=T[p].cover=0;
    if(l+1==r)return;
    int mid=l+r>>1;
    build(lch,l,mid);
    build(rch,mid,r);
}
void update(int p,int l,int r,int v){
    if(T[p].r<=l||T[p].l>=r)return;
    if(T[p].l>=l&&T[p].r<=r){
        T[p].cover+=v;
        push_up(p);
        return;
    }
    update(lch,l,r,v);
    update(rch,l,r,v);
    push_up(p);
}
int f(int x){
    return lower_bound(xx+1,xx+m+1,x)-xx;
}
void make(int x1,int x2,int y1,int y2){
    line[++cnt]=(Line){x1,x2,y1,1};
    xx[cnt]=x1;
    line[++cnt]=(Line){x1,x2,y2,-1};
    xx[cnt]=x2;
}
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    cin>>n;
    for(int x,x1,x2,y1,y2;n--;){
        cin>>x1>>y1>>x2>>y2;
        make(x1,x2,y1,y2);
    }
    sort(line+1,line+cnt+1);
    sort(xx+1,xx+cnt+1);
    m=unique(xx+1,xx+cnt+1)-xx-1;
    build(1,1,m);
    for(int i=1;i<=cnt;i++){
        ans+=T[1].len*(line[i].y-line[i-1].y);
        ans1+=T[1].len1*(line[i].y-line[i-1].y);
        update(1,f(line[i].lx),f(line[i].rx),line[i].inout);
    }
    cout<<ans1/*奇数次*/<<"\n"<<ans-ans1/*总面积减去奇数次面积*/<<"\n";
    return 0;
}//其他为扫描线模板，不再注释

AC 记录