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

chenyizhen · 2025-03-25 20:15:04 · 题解

思路

不同于普通的的扫描线，本题让我们求奇次和偶次覆盖区间，仔细想一下我们不能直接算得是奇次还是偶次，这就要求我们的线段树能够保存每一小块区间的奇偶长度。

struct segment_tree{
    int l,r;//表示区间范围
    int len1,len2,sum;//len1表示奇次，len2表示偶次
}

接下来我们考虑奇次和偶次的转换，完全覆盖父节点的区间一定覆盖子节点，而父节点的父节点（祖父节点）就不会影响子节点的 len1，len2。显然：子节点的区间覆盖次数由且仅由自己和父节点决定。

在区间修改时：

• 父节点没有被完全覆盖时，区间长度由左右儿子节点决定。

if(!t[p].sum){
    t[p].len1=t[p<<1].len1+t[p<<1|1].len1;
    t[p].len2=t[p<<1].len2+t[p<<1|1].len2;
}

• 父节点被完全偶次覆盖时，父节点的真实奇次覆盖为子节点的奇次覆盖和，在通过区间总长减去奇次长度，即为偶次区间长度。

if(!(t[p].sum&1)){
    t[p].len1=t[p<<1].len1+t[p<<1|1].len1;
    t[p].len2=X[t[p].r]-X[t[p].l]-t[p].len1;
}

• 父节点被奇数次完全覆盖时，父节点的真实偶次覆盖为左右儿子子节点奇次覆盖和，后通过区间总长求得奇次覆盖长度。

else{
    t[p].len2=t[p<<1].len1+t[p<<1|1].len1;
    t[p].len1=X[t[p].r]-X[t[p].l]-t[p].len2;
}

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e6+5;
void read(int &a){
    char ch;int f=1,k=0;ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-') f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){k=k*10+ch-'0';ch=getchar();}
    a=k*f;
}
struct Line{
    int l,r,h;
    int mark;
}line[N<<1];
struct segment_tree{
    int l,r;
    int len1,len2,sum;
}t[N<<2];
int n,ans1,ans2,X[N<<1];
bool cmp(Line x,Line y){
    return x.h<y.h;
}

inline void build(int p,int l,int r){
    t[p].l=l,t[p].r=r;
    if(l+1==r) return ;
    int mid=(l+r)>>1;
    build(p<<1,l,mid);
    build(p<<1|1,mid,r);
}

inline void push_up(int p){
    if(!t[p].sum){
        t[p].len1=t[p<<1].len1+t[p<<1|1].len1;
        t[p].len2=t[p<<1].len2+t[p<<1|1].len2;
    }
    else if(!(t[p].sum&1)){
        t[p].len1=t[p<<1].len1+t[p<<1|1].len1;
        t[p].len2=X[t[p].r]-X[t[p].l]-t[p].len1;
    }
    else{
        t[p].len2=t[p<<1].len1+t[p<<1|1].len1;
        t[p].len1=X[t[p].r]-X[t[p].l]-t[p].len2;
    }
}

inline void modify(int p,int l,int r,int w){
    if(X[t[p].r]<=l||X[t[p].l]>=r) return ;
    if(l<=X[t[p].l]&&X[t[p].r]<=r){
        t[p].sum+=w;
        push_up(p);
        return ;
    }
    modify(p<<1,l,r,w);
    modify(p<<1|1,l,r,w);
    push_up(p);
}

signed main(){
    read(n);
    int xa,xb,ya,yb;
    for(int i=1;i<=n;i++){
        read(xa),read(ya),read(xb),read(yb);
        X[i*2-1]=xa,X[i*2]=xb;
        line[2*i-1]=(Line){xa,xb,ya,1};
        line[2*i]=(Line){xa,xb,yb,-1};
    }
    n<<=1;
    sort(line+1,line+1+n,cmp);
    sort(X+1,X+1+n);
    int tot=unique(X+1,X+1+n)-X-1;
    build(1,1,tot);
    for(int i=1;i<n;i++){
        modify(1,line[i].l,line[i].r,line[i].mark);
        ans1+=t[1].len1*(line[i+1].h-line[i].h);
        ans2+=t[1].len2*(line[i+1].h-line[i].h);    
    }
    cout<<ans1<<"\n"<<ans2;
    return 0;
}

补：注意本题build(1,1,tot)，而非 P5490 【模板】扫描线 & 矩形面积并中的build(1,1,tot-1)。我才不会告诉你是我不太明白分析一下：

求管理大大通过！！！ 到这里结束了，点个赞呗！