扫描线

donotctjuntilAFO · 2023-04-26 12:29:20 · 算法·理论

前言

扫描线就是个用时间轴代替一维达到降维目的的算法。

正文

P5490 【模板】扫描线

矩形是二维的，但想象一下，有一条线沿着一条轴匀速扫描，对于每个时刻，只考虑用线段树维护这条线扫到的东西，最后将每个时刻的加起来不就得到面积了吗。

代码：

#include<bits/stdc++.h>
#define f(i,l,r) for(register int i=l;i<=r;++i)
#define F(i,r,l) for(register int i=r;i>=l;--i)
#define int long long
#define ULL unsigned long long
using namespace std;
const int N=2000006;
int n,a[N],ans;
struct node{
    int l,r,h,tag;
    node(int l=0,int r=0,int h=0,int tag=0):l(l),r(r),h(h),tag(tag){}
}L[N];
bool cmp(node a,node b){
    return a.h<b.h;
}
struct SGT{
    int sum,len;
}tree[N<<2];
void pushup(int x,int l,int r){
    if(tree[x].sum){
        tree[x].len=a[r+1]-a[l];
    }
    else{
        tree[x].len=tree[x<<1].len+tree[x<<1|1].len;
    }
}
void build(int l,int r,int x){
    tree[x].len=tree[x].sum=0;
    if(l==r)
        return ;
    int mid=l+r>>1;
    build(l,mid,x<<1);
    build(mid+1,r,x<<1|1);
}
void update(int l,int r,int v,int ll,int rr,int x){
    if(a[rr+1]<=l||r<=a[ll])
        return;
    if(l<=a[ll]&&a[rr+1]<=r){
        tree[x].sum+=v;
        pushup(x,ll,rr);
        return;
    }
    int mid=ll+rr>>1;
    update(l,r,v,ll,mid,x<<1);
    update(l,r,v,mid+1,rr,x<<1|1);
    pushup(x,ll,rr);
}
signed main(){
    scanf("%lld",&n);
    f(i,1,n){
        int x,y,xx,yy;
        scanf("%lld%lld%lld%lld",&x,&y,&xx,&yy);
        a[(i<<1)-1]=x;
        a[i<<1]=xx;
        L[(i<<1)-1]=node(x,xx,y,1);
        L[i<<1]=node(x,xx,yy,-1);
    }
    n<<=1;
    sort(a+1,a+n+1);
    sort(L+1,L+n+1,cmp);
    int len=unique(a+1,a+n+1)-a-1;
    build(1,len-1,1);
    f(i,1,n-1){
        update(L[i].l,L[i].r,L[i].tag,1,len-1,1);
        ans+=tree[1].len*(L[i+1].h-L[i].h);
    }
    printf("%lld",ans);
    return 0;
}

习题：

P1856 [IOI1998] [USACO5.5] 矩形周长Picture

P1502 窗口的星星