【学习笔记】线段树—扫描线补充 (IC_QQQ)

时间:2022-06-28 09:53:02

【学习笔记】线段树—扫描线补充 (IC_QQQ)

(感谢 \(IC\)_\(QQQ\) 大佬授以本内容的著作权。此人超然于世外,仅有 \(Luogu\) 账号 尚可膜拜)

【学习笔记】线段树详解(全)

上题:

    给出N个矩形,求最后所得的图形的面积(周长)。

【学习笔记】线段树—扫描线补充 (IC_QQQ)

比如这个图形,我们去掉多余的线条,看看它最后的图形:

【学习笔记】线段树—扫描线补充 (IC_QQQ)

看到这个花里胡哨的图形,它的面积就是抛开红色的其他部分面积和。

周长呢?就是下面这个图形的红色边长度。

【学习笔记】线段树—扫描线补充 (IC_QQQ)

问题是怎么求,这就需要用到扫线~了。

先解决简单一些的面积:

我们假象有一条垂直于水平面的直线,从左到右依次扫过这个图形,那直线被覆盖的长度(L)只有在每个矩形的左右边界才会变化。

继续上图:

【学习笔记】线段树—扫描线补充 (IC_QQQ)

这个图形被2N(8)条边分成了2N-1(7)个部分。

最后的答案就是这2N-1(7)个部分面积的和。

每个部分的面积又怎么求呢?显而易见 \(S=L*该段的宽\) 。

该怎么实现呢?

我们首先能想到的是,这2N条边至少有3个属性: \(x\),\(y_1\) , \(y_2\)。

如果一个矩形扫描完了呢,肯定要删除吧。

第四个属性就呼之欲出了,记录这是左边界还是右边界。

如果是左边界就记为+1,表示加入了扫描线;

如果是右边界就记为 -1,表示退出了扫描线。

好,想到这里,我们就可以把这2N条边取出来,记做四元组\((x,y_1,y_2,k)\)。

左边界\(k=1\),右边界\(k=-1\)。

然后我们按\(x\)排序,就得到了上面这个图。

可以看到,这条扫描线被纵坐标\(y\)分成了很多段,我们用数组\(c[i]\)记录扫描线第\(i\)段被覆盖的次数。

下一步:

接下来我们就可以模拟扫描线从左到右扫一遍啦!

我们来走一遍流程:

  • 这条扫描线到达了边\(x\),修改扫描线。
  • 扫描线的状态固定了,影响一直持续到下一条边\(x’\)。
  • 我们找到扫描线被覆盖的部分长度和\(H\)。
  • 那这一部分(\(x\)→\(x’\))的面积就找到了:\(H*(x’-x)\),\(ans\)加上这一部分。

\(emmmmm\),可以看到,这个流程并不好走,我们遇到了一抹多的问题。

怎么修改扫描线:

我们取出这条边的纵坐标\(y_1,y_2\),那它们对应着扫描线的哪几段呢?

先把所有的纵坐标放到一个数组\(row\)中,从小到大排序,\(y\)的下标\(val(y)\)就是第几段。

找到了对应的位置,把这些位置加上\(k\)。

H怎么找

至于\(H\)怎么找,我们可以朴素的扫描一遍\(c\)数组,只要\(c[i]>=1\),我们就加上这一段的长度。

又有一个问题:扫描线第\(i\)段的长度怎么找?

这个问题和前面怎么修改扫描线那个问题是相辅相成的。

第\(i\)段的长度就是\(row[i+1]-row[i]\)。

离散化

把所有的\(y\)放进数组\(row\)中,从小到大排序,去重,\(i\)就作为\(row[i]\)的代表数,然后\(val(y)\)(\(y\)的代表数)可以用一个函数查询。下面给出代码:

void pre_work_row(){
sort(row+1,row+1+2*n);//排序
tot=unique(row+1,row+1+2*n)-(row+1);//去重
return;
}
int query(int val){//查询代表数
return lower_bound(row+1,row+1+tot,val)-row;
}

怎么和线段树联系呢:

可以看到,数组\(c\)支持区间修改和查询,这可以用线段树维护,但是不同的题,数组\(c\)存放的值不一样,线段树维护的内容和方式也不一样,我们结合具体的例题讲解。

【题目链接】

好,又领悟了一门新的功法:线~ 求解面积。

接下来,我们就去应用一下这门功法。AKIOI变强指日可待。

窗口的星星 \(Stars\) \(in\) \(Your\) \(Window\) \([P1502]\) \([POJ2482]\)

【标签】线段树/离散化/扫描线

【题解】\(IC\)_\(QQQ\)

\(Atlantis\) \([POJ1151]\)

【标签】线段树/扫描线

矩形周长 \(Picture\) \([USACO5.5]\) \([P1856]\) \([POJ1177]\)

【标签】线段树/扫描线

【题解】Atlantis

描述

有几个古希腊文本包含传说中的亚特兰蒂斯岛的描述,其中一些文本甚至包括岛屿部分地图。但不幸的是,这些地图描述了亚特兰蒂斯的不同区域。您的朋友Bill必须知道地图的总面积。 你(不明智地)自告奋勇写了一个计算这个数量的程序。

输入

输入包含几个测试用例。每个测试用例以整数\(n\)(\(1 \leqslant n \leqslant 100\))的开始。以下\(n\)行描述了每个地图。这些行中的每一行包含四个数字\(x1; y1; x2; y2\)(\(0 \leqslant x1 <x2 \leqslant 100000; 0 \leqslant y1 <y2 \leqslant 100000\)),不一定是整数。值(\(x1; y1\))和(\(x2; y2\))是左下角的坐标。 映射区域的右上角。输入文件由\(0\)终止,不处理它。

输出

样例

样例输入:
2
10 10 20 20
15 15 25 25.5
0 样例输出:
Test case #1
Total explored area: 180.00

分析

这是一道模(mú)板题

这道题呢,数组\(c\) 存的是覆盖次数,我们想想怎么用线段树优化。

这道题中,我们只关心扫描线被覆盖的总长度,除了左右端点 \((l,r)\),至少还要维护区间长度 \(len\),而区间长度受被覆盖次数的影响,肯定还要维护区间的覆盖次数 \(cnt\)。

所以,线段树的每个节点就出来了: \(l,r,len,cnt\)。

如果当前节点 \(cnt \geqslant 1\),\(len=row(r+1)-row(l)\)。

否则,当前节点 \(len=(\)左儿子\()len+(\)右儿子\()len\)。

这道题的特殊之处在于:不需要下传\(cnt\)。

我们想想为什么。

因为四元组 \((x,y_1,y_2,k)\) 是成对出现的,而且\(cnt\)是记录区间被覆盖次数,只要\(cnt>=1\),无论\(cnt\)是多少, \(len=row(r+1)-row(l)\) 是不变的,因此我们没有必要下传 \(cnt\)。

我们可以模拟一下,不下传\(cnt\)对结果有没有影响。

代码实现:

好,接下来,我们就可以来看看这道题怎么写了:

代码看似很长,其实真的很长很亲切的

#include<cstdio>//一定在VJ上选C++
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=205;
int n,nn,tot,Case;//n:矩形个数,nn:边的数量(2*n)
//tot:离散化后,代表数的个数
double ans,row[N];//答案,离散化数组
struct node{
int k;double x,u,v;//横坐标,纵坐标,v>u
}da[N];//四元组
struct aaa{int l,r,cnt;double len;}tree[4*N];//数组大小是重点
bool cmp(node a,node b){return a.x<b.x;}
void pre_reset(){
nn=2*n;ans=0;tot=0;
memset(da,0,sizeof(da));
memset(row,0,sizeof(row));
memset(tree,0,sizeof(tree));
}
void scan_work(){
double a,b,c,d;
for(int i=1;i<=n;i++){
scanf("%lf%lf%lf%lf",&a,&b,&c,&d);
row[i]=b;row[i+n]=d;
da[i].x=a;da[i+n].x=c;
da[i].u=b;da[i+n].u=b;
da[i].v=d;da[i+n].v=d;
da[i].k=1;da[i+n].k=-1;
}
sort(da+1,da+1+nn,cmp);
return;
}
void pre_row_work(){
sort(row+1,row+1+nn);
tot=unique(row+1,row+1+nn)-(row+1);
return;
}
int query(double val){
return lower_bound(row+1,row+1+tot,val)-row;
}
void built_work(int pos,int l,int r){
tree[pos].l=l;tree[pos].r=r;
if(l==r) return;
int mid=(l+r)>>1;
built_work(pos*2,l,mid);
built_work(pos*2+1,mid+1,r);
return;
}
void push_up(int pos){
int ls=pos*2,rs=pos*2+1;
if(tree[pos].cnt)//如果当前区间被覆盖
tree[pos].len=row[tree[pos].r+1]-row[tree[pos].l];
else{//当前区间没有被覆盖
if(tree[pos].l==tree[pos].r) tree[pos].len=0;//只有一段
//也可以不加这个特判,但tree要再开大一倍,防止越界
else tree[pos].len=tree[ls].len+tree[rs].len;
}
return;
}
void change(int pos,int l,int r,int w){
if(l<=tree[pos].l&&r>=tree[pos].r){
tree[pos].cnt+=w;
push_up(pos);//传递信息
return;
}
int mid=(tree[pos].l+tree[pos].r)>>1;
if(l<=mid) change(pos*2,l,r,w);
if(r>mid) change(pos*2+1,l,r,w);
push_up(pos);//传递信息
return;
}
int main(){
while(1){
scanf("%d",&n);
if(n==0) break;
pre_reset();//清零
scan_work();//读入
pre_row_work();//离散化
built_work(1,1,tot-1);//建树
for(int i=1;i<nn;i++){
int u=query(da[i].u);
int v=query(da[i].v)-1;
change(1,u,v,da[i].k);//修改扫描线
double H=tree[1].len;
ans+=(da[i+1].x-da[i].x)*H;
}
printf("Test case #%d\n",++Case);
printf("Total explored area: %.2lf\n\n",ans);
}
}

【题解】矩形周长 Picture

描述

输入

输入文件的第一行是一个整数\(N(0 \leqslant N \leqslant 5000)\),表示有多少个矩形。接下来N行给出了每一个矩形左下角坐标和右上角坐标(所有坐标的数值范围都在\(-10000\)到\(10000\)之间)。所有矩形顶点的坐标都是整数。

输出

输出文件只有一个正整数,表示最终图形的周长。

举例说明

这是给出的图形:

【学习笔记】线段树—扫描线补充 (IC_QQQ)

这是最终的图形:

【学习笔记】线段树—扫描线补充 (IC_QQQ)

尝试解决:

老规矩,取出\(2N\)条边,记为四元组:\((x,y_1,y_2,k)\)。左边界\(k=1\),右边界\(k=-1\)。

以\(x\)为关键元从小到大排序这些四元组。

对所有的\(y\)离散化,得到\(tot\)个代表数。

扫描线被分成了\(tot-1\)段。

然后呢?然后怎么办:

我们模拟扫一遍,列出扫描线的所有状态,大家想想怎么解决。

通过上面的思索,我们发现,\(c[i]\) 还是表示第\(i\)段被覆盖的次数。

修改和\(Atlantis\)也一模一样:

  • 修改扫描线。
  • 查询扫描线被覆盖长度\(len\)。

唯一有所不同的是,如何累加\(ans\)。

经过我们的探究,高就是\(len_i-len_{i-1}\)。

长呢?这需要在扫描\(c[i]\)求\(len\)时多做一步,求出扫描线被覆盖的段数\(num\)。

并且前面我们探究过了,长就是\(x_{i+1}-x_i*num*2\)。

\(ans\)累加上高和长就好了。

用线段树优化:

对四元组排序时,\(x\)相等怎么办?

根据前面的分析,很容易想到,需要维护区间被覆盖次数\(cnt\),区间长度\(len\),区间的被覆盖段数\(num\)。

前面两个大家都会写吧,重点是新多出来的这个\(num\)。

我们再来模拟修改。

如果当前节点\(cnt\geqslant 1\),\(num=1\)。

否则,\(num=(\)左儿子\()num+(\)右儿子\()num\)。

但是呢,事情没那没简单,如果遇到这种情况怎么办?

下面来看一张图:

【学习笔记】线段树—扫描线补充 (IC_QQQ)

咳咳,懒得画图了。

总之,我们线段树还需要维护两个变量\(lg,rg\),记录该区间的左右端点是否被覆盖。

如果当前节点\(cnt\geqslant1\),\(lg=1,rg=1\)。

否则,\(lg=(\)左儿子\()lg,rg=(\)右儿子\()rg\)。

统计\(num\)时,如果碰到上述情况(\(cnt<1\),左儿子\(rg=1\),右儿子\(g=1\)),\(num--\)。

代码实现:

#include<cstdio>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
const int N=1e4+5;
int n,nn,ans;
int tot,last;//last:上次扫描线被覆盖长度
int row[N];
struct node{int x,u,v,k;}da[N];
struct aaa{
int cnt,num,len;
bool lg,rg;
}tree[4*N];
bool cmp(node a,node b){
if(a.x!=b.x) return a.x<b.x;
return a.k>b.k;
}
void pre_work_row(){
sort(row+1,row+1+nn);
tot=unique(row+1,row+1+nn)-(row+1);
return;
} int query(int x){
return lower_bound(row+1,row+1+tot,x)-row;
}
void Pushup(int pos,int pl,int pr){
int ls=pos*2,rs=pos*2+1;
if(tree[pos].cnt){
tree[pos].num=1;
tree[pos].len=row[pr+1]-row[pl];
tree[pos].lg=tree[pos].rg=1;
}
else{
tree[pos].num=tree[ls].num+tree[rs].num;
if(tree[ls].rg&&tree[rs].lg) tree[pos].num--;
tree[pos].len=tree[ls].len+tree[rs].len;
tree[pos].lg=tree[ls].lg;
tree[pos].rg=tree[rs].rg;
}
return;
}
void change(int pos,int pl,int pr,int l,int r,int w){
if(l<=pl&&r>=pr){
tree[pos].cnt+=w;
Pushup(pos,pl,pr);
return;
}
int mid=(pl+pr)>>1;
if(l<=mid) change(pos*2,pl,mid,l,r,w);
if(r>mid) change(pos*2+1,mid+1,pr,l,r,w);
Pushup(pos,pl,pr);
return;
}
int main(){
scanf("%d",&n);
int a,b,c,d;nn=2*n;
for(int i=1;i<=n;i++){
scanf("%d%d%d%d",&a,&b,&c,&d);
row[i]=b;row[i+n]=d;
da[i].x=a;da[i+n].x=c;
da[i].u=b;da[i+n].u=b;
da[i].v=d;da[i+n].v=d;
da[i].k=1;da[i+n].k=-1;
}
pre_work_row();
sort(da+1,da+1+nn,cmp);
for(int i=1;i<=nn;i++){
last=tree[1].len;
change(1,1,tot-1,query(da[i].u),query(da[i].v)-1,da[i].k);
ans+=abs(tree[1].len-last);
ans+=(da[i+1].x-da[i].x)*tree[1].num*2;
}
printf("%d",ans);
return 0;
}