线段树+扫描线

经典的扫描线问题

首先将一个矩形看作由竖着的两条边和横着的两条边构成

那分成两次考虑，一次考虑竖边，一次考虑横边

首先考虑横边

如图两个矩形，现将横边擦去，留下竖边，将平面划分成3个区域

在代码实现时，可以从左到右记录端点

那么现在想象一条平行于横边的扫描线不断从下往上扫

当扫到一个矩形的下边，将这条矩形的下边包含的区间覆盖

当扫到一个矩形的上边，将这条矩形的上边包含的区间去除覆盖

那么对于这些被竖线划分的区域，建立一棵线段树维护这些区间是否被覆盖

如最底下的矩形下边，覆盖区间2,3

那么如何统计答案

答案就是上一次线段树维护的总区间被覆盖的长度-当前线段树维护的总区间覆盖的长度的绝对值

如上图，扫描到第2边，上一次覆盖2,3，那此处增加为1区间

那么线段树中维护这个区间被完全覆盖的次数和被覆盖的长度即可

#include <iostream>

#include <algorithm>

#include <map>

#include <cstdio>

#define inf (int)1e9

using namespace std;

int n,w,last,ans;

struct node

{

    int a,b,c,d;

}p[5100];

struct tree

{

    int l,r,sum;

    int len;

}sh[100000];

struct edge

{

    int l,r,num,kind;

}a[11000];

bool cmp(edge a,edge b)

{

    return (a.num<b.num || (a.num==b.num && a.kind>b.kind));//注意如果同一高度的话，先处理下边的

}

void pushup(int x)

{

    if (sh[x].sum>0)//如果当前被完全覆盖，那么当前区间被覆盖的长度为r-l+1

      sh[x].len=sh[x].r-sh[x].l+1;

    else

    if (sh[x].l==sh[x].r)//叶子结点

      sh[x].len=0;

    else

      sh[x].len=sh[x+x].len+sh[x+x+1].len;//一般情况

}

void build(int x,int ll,int rr)

{

    sh[x].l=ll;

    sh[x].r=rr;

    sh[x].sum=sh[x].len=0;

    if (ll==rr)

      return;

    int mid;

    mid=(ll+rr)>>1;

    build(x+x,ll,mid);

    build(x+x+1,mid+1,rr);

}

void change(int x,int ll,int rr,int v)

{

    if (sh[x].l>=ll && sh[x].r<=rr)

    {

        sh[x].sum+=v;

        pushup(x);

        return;

    }

    int mid;

    mid=(sh[x].l+sh[x].r)>>1;

    if (ll<=mid)

      change(x+x,ll,rr,v);

    if (rr>mid)

      change(x+x+1,ll,rr,v);

    pushup(x);

}

int main()

{

    scanf("%d",&n);

    for (int i=1;i<=n;i++)

      scanf("%d%d%d%d",&p[i].a,&p[i].b,&p[i].c,&p[i].d);

    for (int i=1;i<=n;i++)//记录前扫描线要扫到的边

    {

        w++;

        a[w].l=p[i].a;a[w].r=p[i].c;

        a[w].kind=1;a[w].num=p[i].b;//下边

        w++;

        a[w].l=p[i].a;a[w].r=p[i].c;

        a[w].kind=-1;a[w].num=p[i].d;//上边

    }

    build(1,-10000,10000);

    sort(a+1,a+1+w,cmp);

    last=0;//上一次答案

    for (int i=1;i<=w;i++)

    {

        change(1,a[i].l,a[i].r-1,a[i].kind);

        ans+=abs(last-sh[1].len);

        last=sh[1].len;

    }

    w=0;//处理竖边

    for (int i=1;i<=n;i++)

    {

        w++;

        a[w].l=p[i].b;a[w].r=p[i].d;

        a[w].kind=1;a[w].num=p[i].a;

        w++;

        a[w].l=p[i].b;a[w].r=p[i].d;

        a[w].kind=-1;a[w].num=p[i].c;

    }

    build(1,-10000,10000);

    sort(a+1,a+1+w,cmp);

    last=0;

    for (int i=1;i<=w;i++)

    {

        change(1,a[i].l,a[i].r-1,a[i].kind);

        ans+=abs(last-sh[1].len);

        last=sh[1].len;

    }

    printf("%d\n",ans);

}

巴特西

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

线段树+扫描线

最新文章

热门文章