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

· · 题解

题目

前言

本篇主要是对针对所有分别统计奇偶覆盖次数的题解作说明。

\texttt{upd：2025.3.7.}

思路

和 P5490 的模版扫描线不同，在统计总长度时可以分成 len1 和 len2 分别记录奇偶次数的完全覆盖总长度。所以除区间修改外其余内容与模版扫描线大体相同。

对于线段树结合扫描线的区间修改，目前的几篇题解在奇偶处理时都没有一个较明确的推导，我自己的推导如下：

先给出一个图，方便操作（有点丑陋，见谅）:

说明一下这个图为什么有些点重了，因为我是按边分的区间。

因为在区间修改时只要满足：

if(l<=X[s]&&X[t]<=r){//l-r是当前扫到的线，X[s]-X[t]是一个区间
    d[p].cnt+=c;//只要可以完全覆盖就 return 即不会传到子树 
    pushup(p);
    return;
}

结论说明：这样的话，完全覆盖次数就不会传到子树。正常点说，就是图中的父节点的完全覆盖次数永远不可能传到子节点，但子节点的实际完全覆盖次数是父节点的完全覆盖次数加上子节点的完全覆盖次数。对于父节点的父节点我称爷爷节点与原父节点的子节点的关系，因为爷爷节点被完全覆盖也会把原父节点和子节点完全覆盖，大不了原父节点和子节点的奇偶同时加或同时减，所以不影响原父节点与子节点的传递（偶加减偶得偶，偶加减奇得奇，奇加减奇得偶）。

所以在区修时可得如下 3 种情况：

对于没有被完全覆盖的情况，即 !d[p].cnt：此时明显由左右子树转移。

if(!d[p].cnt)//没有完全覆盖由左右子树转移 
    d[p].len1=d[p<<1].len1+d[(p<<1)|1].len1,
    d[p].len2=d[p<<1].len2+d[(p<<1)|1].len2;

设子节点奇偶总长为 Llen1,Llen2，目前即父节点奇偶总长为 len1,len2，则有：

对于父节点被奇数次完全覆盖的情况，即 d[p].cnt&1。根据结论，有子节点目前实际偶数次完全覆盖是父节点完全覆盖次数加子节点偶数次完全覆盖次数等于奇数次完全覆盖，而实际奇覆盖是父节点完全覆盖次数加子节点奇数次完全覆盖次数等于偶数次完全覆盖。也就是说，子节点奇数次覆盖实际是偶数次覆盖，所以 len2 由 Llen1 转移；子节点偶数次覆盖实际是奇数次覆盖，所以 len1 由 Llen2 转移。对于转移，因为奇偶面积并之和为总面积并，但由于 Llen2 可能未传入偶数为 0 的面积并，当且仅当被覆盖次数原始为 0 但实际覆盖次数在祖先节点未下传；而 Llen1 为奇数覆盖其覆盖次数大于 0 所以该有的值肯定是被更新过的，特殊的当祖先有偶数次覆盖可能是不会更新 Llen1，但不影响，因为加了偶数次仍是原来奇数覆盖的长度。所以，先算得 len2，再通过总长算出 len1。

if(d[p].cnt&1)
    d[p].len2=d[p<<1].len1+d[(p<<1)|1].len1,//len2=Llen1
    d[p].len1=X[r]-X[l]-d[p].len2;//总长-len2

对于父节点被偶数次完全覆盖的情况，即 !(d[p].cnt&1)，根据结论，可同理推导。

//转移过程同奇数覆盖情况 
    d[p].len1=d[p<<1].len1+d[(p<<1)|1].len1,
    d[p].len2=X[r]-X[l]-d[p].len1;

点个免费的赞再走吧！

#include<bits/stdc++.h>
using namespace std;
const int N=1e6+5;
#define x1 X1
#define x2 X2
#define y1 Y1
#define y2 Y2
#define int long long
int n,m,X[N<<1];
struct sb{
    long long y,l,r,t;
}ld[N<<1];
struct ssb{
    long long l,r,cnt,len1,len2; 
}d[N<<2];
bool cmp(sb x,sb y){
    return x.y<y.y;
}
void js(int l,int r,int p){
    d[p]={l,r,0,0,0};
    if(l+1==r)return;
    int mid=(l+r)>>1;
    js(l,mid,p<<1),js(mid,r,(p<<1)|1);
}
void pushup(int p){
    int l=d[p].l,r=d[p].r;
    if(!d[p].cnt)
        d[p].len1=d[p<<1].len1+d[(p<<1)|1].len1,
        d[p].len2=d[p<<1].len2+d[(p<<1)|1].len2;
    else if(d[p].cnt&1)
        d[p].len2=d[p<<1].len1+d[(p<<1)|1].len1,
        d[p].len1=X[r]-X[l]-d[p].len2;
    else
        d[p].len1=d[p<<1].len1+d[(p<<1)|1].len1,
        d[p].len2=X[r]-X[l]-d[p].len1;
}
void dsb(int c,int l,int r,int p){
    int s=d[p].l,t=d[p].r;
    if(r<=X[s]||X[t]<=l)return;
    if(l<=X[s]&&X[t]<=r){
        d[p].cnt+=c;
        pushup(p);
        return;
    }dsb(c,l,r,p<<1),dsb(c,l,r,(p<<1)|1);
    pushup(p);
}
signed main(){
    ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        int x1,x2,y1,y2;
        cin>>x1>>y1>>x2>>y2;
        X[(i<<1)-1]=x1,X[i<<1]=x2;
        ld[(i<<1)-1]={y1,x1,x2,1},ld[i<<1]={y2,x1,x2,-1};
    }n<<=1;
    sort(X+1,X+1+n),sort(ld+1,ld+1+n,cmp);
    m=unique(X+1,X+1+n)-X-1;
    js(1,m,1);
    long long ans1=0,ans2=0;
    for(int i=1;i<n;i++){
        dsb(ld[i].t,ld[i].l,ld[i].r,1);
        ans1+=d[1].len1*(ld[i+1].y-ld[i].y);
        ans2+=d[1].len2*(ld[i+1].y-ld[i].y);
    }cout<<ans1<<'\n'<<ans2;
    return 0;
}