线段树扫描线详解

OI比赛中扫描线是一种很常用的算法，矩形周长是一个模板题。

题目链接

基本思想

比如，对于下面的三个矩形：

        想象有一条扫描线，从下往上扫描完整个图案，每遇到一条上边或者下边就停下来：

    然后每次停下后对区间进行处理，用一个ans代表当前周长，最后ans就是答案。

代码实现

    首先，要先把矩形拆成上边和下边，用1和-1分别代表上边和下边。然后按高度排序，这样数组从前往后处理就相当于扫描线从下往上扫描。如果是下边，就在对应区间上加1，如果是上边，就在对应区间上减1。

    在整个区间上建一棵线段树：

#define lson o<<1
#define rson o<<1|1
#define mid (l+r)/2
struct Tree
{
    int sum;//整个区间被整体覆盖了几次（类似lazytag，但不下传)
    int num;//整个区间被几条互不相交的线段盖（比如，[1,2],[4,5]则为2，[1,3],[4,5]则为1（我习惯用闭区间），[1,4],[2,2],[4,4]也为1）
    int len;//整个区间被覆盖的总长度
    bool lflag;//左端点是否被覆盖（合并用）
    bool rflag;//右端点是否被覆盖（合并用）
}//如果不懂也没有关系，接着往下看

那么pushup要怎么写呢？

void pushup(int o,int l,int r)
{
    if(tree[o].sum)//此区间之前被一整个线段覆盖过
    {
        tree[o].num=1;
        tree[o].len=r-l+1;
        tree[o].lflag=tree[o].rflag=1;
    }
    else if(l==r)//这是一个叶节点
    {
        tree[o].num=0;
        tree[o].len=0;
        tree[o].lflag=tree[o].rflag=0;
    }
    else//一般情况
    {
        tree[o].num=tree[lson].num+tree[rson].num;
        if(tree[lson].rflag==tree[rson].lflag)tree[o].num--;//flag的用处
        tree[o].len=tree[lson].len+tree[rson].len;
        tree[o].lflag=tree[lson].lflag;
        tree[o].rflag=tree[rson].rflag;
        //注意：sum不会被修改，只有当它被一整个线段覆盖时才会修改
    }
}

有了pushup，add函数就好写了：

void add(int o,int l,int r,int from,int to,int value)
//此区间为[l,r],待修改区间为[from,to]，添加值为value。
{
    if(l>=from&&r<=to)//被整个覆盖
    {
        tree[o].sum+=value;
        pushup(o,l,r);
        return;
    }
    if(from<=mid)add(lson,l,mid,from,to,value);
    if(to>mid)add(rson,mid+1,r,from,to,value);
    pushup(o,l,r);
}

流程

Step 0：build

Step 1：add(1,1,6,1,5,1)

先递归处理：

再pushup：

Step 2:add(1,1,6,2,3,1)

Step 3:add(1,1,6,4,5,1)

(懒得分开写了）

递归处理，pushup：

Step 4:add(1,1,6,1,5,-1)

Step 5:add(1,1,6,2,3,-1)

Step 6:add(1,1,6,5,6,-1)

至此，总算说完了线段树的修改。

    突然想起一个很严肃的事情来：答案怎么统计？

    对于横边，相邻两次修改的区间覆盖长度差（就是tree[root].len的差）加起来就是答案（不理解的自己想办法理解，反正我不理解）；

    对于竖边，你可以再让扫描线从左到右扫一遍~~不过还是说简单法吧。我们需要记录整个区间有多少个端点（包含在线段内不算），然后用它乘上相邻两次修改的高度差。

    怎么记录呢？

    对了，就是tree[root].num*2*(h2-h1)（num的作用在这里）

    好了，下面是完整代码：

#include<cstdio>
#include<algorithm>
#include<cstring>
#define lson o<<1
#define rson o<<1|1
#define mid (l+r)/2
using namespace std;
struct Edge
{
int left;
int right;
int height;
int flag;
}e[10005];
struct Tree
{
int sum;
int num;
int len;
bool lflag;
bool rflag;
}tree[100005];
int n,mx=-2147483647,mn=2147483647,edgenum,ans,last;
void add_edge(int l,int r,int h,int f)
{
e[++edgenum].left=l;
e[edgenum].right=r;
e[edgenum].height=h;
e[edgenum].flag=f;
}
bool cmp(Edge a,Edge b)
{
return a.height<b.height||a.height==b.height&&a.flag>b.flag;
}
void pushup(int o,int l,int r)
{
if(tree[o].sum)
{
tree[o].num=1;
tree[o].len=r-l+1;
tree[o].lflag=tree[o].rflag=1;
}
else if(l==r)
{
tree[o].len=0;
tree[o].num=0;
tree[o].lflag=tree[o].rflag=0;
}
else
{
tree[o].len=tree[lson].len+tree[rson].len;
tree[o].num=tree[lson].num+tree[rson].num;
if(tree[lson].rflag&&tree[rson].lflag)tree[o].num--;
tree[o].lflag=tree[lson].lflag;
tree[o].rflag=tree[rson].rflag;
}
}
void add(int o,int l,int r,int from,int to,int value)
{
if(l>=from&&r<=to)
{
tree[o].sum+=value;
pushup(o,l,r);
return;
}
if(from<=mid)add(lson,l,mid,from,to,value);
if(to>mid)add(rson,mid+1,r,from,to,value);
pushup(o,l,r);
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
{
int x1,y1,x2,y2;
scanf("%d%d%d%d",&x1,&y1,&x2,&y2);
mx=max(mx,max(x1,x2));
mn=min(mn,min(x1,x2));
add_edge(x1,x2,y1,1);
add_edge(x1,x2,y2,-1);
}
if(mn<=0)
{
for(int i=1;i<=edgenum;i++)
{
e[i].left+=-mn+1;
e[i].right+=-mn+1;
}
mx-=mn;
}
sort(e+1,e+edgenum+1,cmp);
for(int i=1;i<=edgenum;i++)
{
add(1,1,mx,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++;
add(1,1,mx,e[i].left,e[i].right-1,e[i].flag);
}
ans+=abs(tree[1].len-last);
last=tree[1].len;
ans+=tree[1].num*2*(e[i+1].height-e[i].height);
}
printf("%dn",ans);
return 0;
}

最后给两个卡死我的样例：

样例输入1：

7
-15 0 5 10
-5 8 20 25
15 -4 24 14
0 -6 16 4
2 15 10 22
30 10 36 20
34 0 40 16

样例输出1：

228

样例输入2：

2
0 0 4 4
0 4 4 8

样例输出2：

24

最后

以上就是危机芝麻为你收集整理的线段树扫描线求矩形周长详解线段树扫描线详解的全部内容，希望文章能够帮你解决线段树扫描线求矩形周长详解线段树扫描线详解所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。