[学习笔记22] 扫描线周长并学习笔记

· · 个人记录

扫描线的具体想法是将一个不规则多边形(仅有竖直与水平边)切割成若干规则矩形，再对这些规则矩形进行周长贡献计算。

如下图为 oi-wiki 上扫描线面积并的图

周长处理与其类似，我们分为横边与竖边。这里选择扫描线向上扫描横边(实际根据喜好均可)，步骤如下:

  1. 先将每条横边按小到大排序。
  2. 每个矩形一定存在一条上边与下边，我们将下边视为加边，上边视为减边。在高度相同的情况下按先加后减的顺序处理。
  3. 每扫描到一条高度不同的新边便开始计算贡献。两次扫描到的长度之差便是需要累加的贡献。

第一次学扫描线的到这里应该都会出现一个疑问。扫描长度之差作为总周长贡献的正确性保证吗，是否会出现重复算、漏算、错算的情况。接下来对这三种情况依次分析：

1.重复算，每出现一条高度不同的线我们才会对其计算一次，不可能出现一条线被重复算的情况。

2.漏算，解释同一，我们对同一高度的线段也会一同处理，保证每一条线段都会被计算。

3.错算，这个略有难度。

试想一下，对于上一次计算的长度，其中的部分长度到现在要么仍然存在，要么已经删除。因为我们每出现一次新线段就对其计算，所以对于这个长度中的每一条线段，最多只可能发生了一次操作(要么删除，要么仍然存在)。也就是说，我们对扫描线长度造成长度的变化一定是以上一条扫描线为基础的。

造成变化量的原因是如果删除且删除线段区间仅被覆盖一次(矩形上边裸露)，或者加入一条线段进从未被覆盖的区间(矩形下边裸露)。

对于新线段的加入(下边)和删除(上边)来说，对周长的贡献是他们所造成的变化量 Δl 。先忽略线段树的具体做法，正确的处理他们每次所变化的长度量 Δl 。线段树存储的便是这个扫描线的长度，在对所有长度量计算完之后，与上一次的差便是 Δl 。这便是正确性。

横边处理完之后，只需要再维护两条扫描线之间的简单矩形区域中有几条未被覆盖的竖边，个数乘上长度，全部算完答案就出来了。

之前处理高度相同的线段时的排序原因：我们在处理的时候，是先将新线段拍入线段树再计算贡献值的对吧。如果先加入删边再加入上边，看下图：

我们先处理删边，就会加一次 AC ，再加上 BD ,就会重复计算 BC 两次（实际我们仅想计算 AC+CD ）。

但先加入边 BD ,长度只比上次多了 CD 。再删边因为 BC 此时被覆盖两次所以减完之后仍然剩余不被计算。

这是因为我们删边可能会与加边有重合，很明显重合部分不需要被计算，因此要先加边再删边。

代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
struct edge{
    int left,right,height,flag;
    friend bool operator<(edge x,edge y){
        if(x.height==y.height) return x.flag>y.flag;
        return x.height<y.height;
    }
}e[N<<1];
int idx;
void add(int l,int r,int h,int f){
    e[++idx]={l,r,h,f};
}
int n;
int mx=-1e9,mn=1e9;
struct tree{
    int sum;
    int num;
    int len;
    bool lflag,rflag;
    int l,r;
}op[N<<2];
#define lson num<<1
#define rson num<<1|1
void push_up(int num){
    if(op[num].sum){
        op[num].num=1;
        op[num].len=op[num].r-op[num].l+1;
        op[num].lflag=op[num].rflag=1;
    }
    else if(op[num].l==op[num].r){
        op[num]={0,0,0,0,0,op[num].l,op[num].r};
    }
    else{
        op[num].num=op[lson].num+op[rson].num;
        op[num].len=op[lson].len+op[rson].len;
        if(op[lson].rflag&&op[rson].lflag) op[num].num--;
        op[num].lflag=op[lson].lflag;
        op[num].rflag=op[rson].rflag;   
    }
}
void build(int num,int l,int r){
    op[num].l=l,op[num].r=r;
    if(l==r) return;
    int mid=(l+r)>>1;
    build(lson,l,mid);
    build(rson,mid+1,r);
}
void update(int num,int l,int r,int k){
    if(l<=op[num].l&&op[num].r<=r){
        op[num].sum+=k;
        push_up(num);
        return;
    }
    if(l>op[num].r||r<op[num].l) return;
    update(lson,l,r,k);
    update(rson,l,r,k);
    push_up(num);
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        int a1,b1,a2,b2;
        cin>>a1>>b1>>a2>>b2;
        mx=max(mx,a2);
        mn=min(mn,a1);
        add(a1,a2,b1,1);
        add(a1,a2,b2,-1);
    }
    if(mn<=0){
        for(int i=1;i<=idx;i++){
            e[i].left+=-mn+1;
            e[i].right+=-mn+1;
        }
        mx-=mn;
    }
    sort(e+1,e+idx+1);
    build(1,1,mx);
    int ans=0,last=0;
    for(int i=1;i<=idx;i++){
        update(1,e[i].left,e[i].right-1,e[i].flag);
        while(e[i].height==e[i+1].height&&e[i].flag==e[i+1].flag){
            i++;update(1,e[i].left,e[i].right-1,e[i].flag);
        }
        ans+=abs(op[1].len-last);
        last=op[1].len;
        ans+=op[1].num*2*abs(e[i+1].height-e[i].height);
    }
    cout<<ans;
    return 0;
}