【扫描线】学习笔记

【模板】扫描线

题目描述

求

输入格式

第一行一个正整数

接下来 $x_1, y_1, x_2, y_2x1,y1,x2,y2，表示一个矩形的左下角坐标为 (x_1, y_1)(x1,y1)，右上角坐标为 (x_2, y_2)(x2,y2)。$

输出格式

一行一个正整数，表示

输入输出样例

输入 #1

2
100 100 200 200
150 150 250 255

输出 #1

说明/提示

对于 $20\%20% 的数据，1 le n le 10001≤n≤1000。$

对于 $100\%100% 的数据，1 le n le 10^5, 0 le x_1 < x_2 le 10^9, 0 le y_1 < y_2 le 10^91≤n≤105,0≤x1<x2≤109,0≤y1<y2≤109。$

$扫描线的思想主要思想就是分割图形。$

$扫描线的方向没有规定，这里用从左到有说明扫描线是如何分割图形的。$

$我们可以将一个矩形转化成两条边，及左边和右边平行y轴的两条边。$

$一条边到另一条边的距离乘边的长度，就是这个矩形的面积。$

$只需要处理这每个矩形的两条边对扫描线长度取值的影响即可。$

$将所有的边按x的值排列，这样我们可以按边的编号从大到小一个一个扫描。$

$当扫描到边i，$ $如果是矩形左边的边，那么这个矩形对面积的贡献就开始了。$

$如果没有其他矩形(边)的贡献，那么这条边将会矩形并的面积产生 len*( x(i+1)-x(i) )，$

$len是i线段的长，x(i+1)-x(i)是i到下一条线段的长。$

$这是显然的，但如何题目要求的是多个矩形的共同产生的影响。$

$如何记录他们的影响？$

$如果是左边(y1,y2)，那么我们让区间(y1,y2)出现的次数+1，(有一个新矩形出现)$

$如果是右边(y1,y2)，那么我们让区间(y1,y2)出现的次数-1。(这个矩形已经扫完了)$

$如果一个区间出现的cnt>=1，则这个区间对扫描线贡献(y2-y1)的长度(区间长)。$

$否则他贡献的长度为他的两个自区间贡献的长度。$

$那么我们只需要对这条扫描线建立一个线段树，维护他的cnt和len即可。$

$由于笔者之前写的段树几乎都是点数，没有区间树。$

$也鉴于智商问题，刚开始对区间树的一些操作有一些排斥，所以花了很长时间才理解。$

$基于线段树，我们只要先对每条线段记录y1,y2,和val，$ $val的取值是1或-1。$

$然后枚举每条边，change一下他们的cnt和len。$

$这当前扫描线截取的长度为tree[1].len。用这个len乘i到下一条边的x差，就是这一次割出来的面积。$

$下面讲讲区间树和点数的一下小差别。$

$比如说，我们要修改[5,8]。$

$那么[1,5]和[8,10]与它有没有交集？$

$显然，对于点集[1,5]，[8,10]是有的，而区间[1,5]，[8,10]和[5,8]是没有交集的。$

$那该这么处理区间树的边界问题。$

$刚开始对于树上每个点，都设置一个l和r。$

$但我们实际处理时，这个节点管辖的区间是[l,r+1]$

$假如我们要处理的区间为[y1,y2]，那么我们实际去找范围在[y1,y2-1]范围的点（线段树实质是点树）。$

$这样一波操作，我们避免了在处理边界时，引入端点相同，却没有交点的区间。$

$还有不要忘记离散化。$

$贴上代码附上简洁的注释。$

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ls (k<<1)
#define rs (k<<1|1)
#define ll long long
using namespace std;
const ll N=1e6;
ll n,cnt,ans;
ll a[N<<4];//空间还是大一点好。~惨痛的教训~
struct node{
    ll l,r,len,cnt;
}tree[N<<4];
struct node1{
    ll x,y1,y2,flag;
    bool operator < (const node1 &temp) const{
        return x<temp.x;
    }
}seg[N<<4];
inline void read(ll &x){
    x=0;
    char ch=getchar();
    while(ch<'0'||ch>'9') ch=getchar();
    while(ch>='0'&&ch<='9') x=(x<<3)+(x<<1)+(ch^48),ch=getchar();
}
inline void build(ll k,ll x,ll y){
    tree[k].l=x,tree[k].r=y;
    if(x==y) return;
    ll mid=x+y>>1;
    build(ls,x,mid);
    build(rs,mid+1,y);
}
inline void updata(ll k){
    if(tree[k].cnt) tree[k].len=a[tree[k].r+1]-a[tree[k].l];//cnt>=1,len为区间长。
    else tree[k].len=tree[ls].len+tree[rs].len;//否则为子区间len和。
}
inline void change(ll k,ll x,ll y,ll l,ll r,ll val){
    if(x>=l&&y+1<=r){//实际处理的[l,r]，我们找[l,r-1]
        tree[k].cnt+=val;
        updata(k);
        return;
    }
    if(x>=r||y<l) return;
//左端点如果等，那也没有交集。而右端点可以等。
//举个例子，当我们要找真实区间[l,r]为[3,5],若[x,y]为[5,8],没有交集，若为[3,3](对于真实区间为[3,4])有交集。
    ll mid=x+y>>1;
    change(ls,x,mid,l,r,val);
    change(rs,mid+1,y,l,r,val);
    updata(k);//由下到上大updata会比较好实现。
}
int main()
{
    ll i,j,x1,x2,y1,y2;
    read(n);
    for(i=1;i<=n;i++){
        read(x1),read(y1),read(x2),read(y2);
        a[++cnt]=y1;
        a[++cnt]=y2;//离散化数组。
        seg[(i<<1)-1].x=x1;
        seg[(i<<1)].x=x2;
        seg[(i<<1)-1].y1=seg[i<<1].y1=y1;
        seg[(i<<1)-1].y2=seg[i<<1].y2=y2;
        seg[(i<<1)-1].flag=1;
        seg[(i<<1)].flag=-1;
　　　　//左边val=1，右边val=-1。
    }
    sort(a+1,a+cnt+1);
    sort(seg+1,seg+(n<<1)+1);
    cnt=unique(a+1,a+1+cnt)-a-1;
    build(1,1,cnt);
    for(i=1;i<=n<<1;i++){
        seg[i].y1=lower_bound(a+1,a+1+cnt,seg[i].y1)-a;
        seg[i].y2=lower_bound(a+1,a+1+cnt,seg[i].y2)-a;//找到每个线段在a中的映射。
    }
    for(i=1;i<=n<<1;i++){
        y1=seg[i].y1,y2=seg[i].y2;
        change(1,1,cnt,y1,y2,seg[i].flag);
        ans+=(seg[i+1].x-seg[i].x)*tree[1].len;//分割图形，更新答案。
    }
    printf("%lld",ans);
}