掃描線學(xué)習(xí)筆記
今天初學(xué)了掃描線，發(fā)一篇學(xué)習(xí)筆記鞏固一下
掃描線能干什么
- 計(jì)算矩形面積的并
- 計(jì)算矩形周長(zhǎng)的并
- 其他
引入
如下圖所示，給定平面直角坐標(biāo)系內(nèi)N個(gè)矩形，求矩形的面積并，定義面積的并為矩形并集覆蓋坐標(biāo)系的面積和
正文部分
面積并：
通過觀察，我們發(fā)現(xiàn)，對(duì)于矩形面積的并，可以通過以每個(gè)矩形左右邊為分界，分成若干小的規(guī)則矩形，所以，我們引入了一種新的思想——掃描線。
顧名思義，這種思想在坐標(biāo)系內(nèi)構(gòu)想了一條從左到右掃描整個(gè)坐標(biāo)系的直線，它在每個(gè)矩形的邊停頓并更新答案，如下圖，紅線即為掃描線，這種思想即為掃描線法。
那么我們思考最終答案，根據(jù)引入所言，不難注意到，我們?cè)谕ㄟ^掃描線把面積并分成了若干規(guī)則圖形，通過矩形計(jì)算公式即可輕易計(jì)算出每部分的答案，具體而言，我們記錄每一個(gè)掃描線停頓位置的橫坐標(biāo)，定為\(x_1 , x_2 ,x_3 ,x_n\) 對(duì)于每一個(gè)位置矩形的面積我們可以得出\(S=(x_i-x_{i-1})\times h\)(\(h\)為掃描線此時(shí)高度),最后，各掃描線停頓位置之和即為所求。
我們?nèi)绾尉S護(hù)答案呢，對(duì)于每一個(gè)停頓位置，我們可以有四元組\((x,y1,y2,d)\)，其中，x為橫坐標(biāo)，\(y1,y2\)為在\(x_i\)處掃描線與整個(gè)圖形的最低交點(diǎn)和最高交點(diǎn),對(duì)于左邊界，\(d=1\)，對(duì)于右邊界\(d=-1\),如圖
同時(shí)，我們給每一個(gè)經(jīng)過縱坐標(biāo)排序，維護(hù)\(raw\)數(shù)組，對(duì)于\(raw[i]\)，表示從\(y_i\)的坐標(biāo)，掃描線被每條上下邊界分成若干段，對(duì)于一段\([y_{i-1},y_i]\)，可以用\(raw\)數(shù)組表示。
我們?cè)倬S護(hù)一個(gè)數(shù)組\(c\)，\(c[i]\)表示到目前位置，第\(i\)個(gè)區(qū)間段被覆蓋的次數(shù)，按\(x\)升序遍歷四元組，每次給\([y_1,y_2]\)每一段加上\(d\)，\(c[i]>0\)表示這個(gè)區(qū)間目前仍被覆蓋，\(\sum_{c[i]>0}{raw[i]-raw[i-1]}\)即為掃描線到當(dāng)前節(jié)點(diǎn)的\(h\)，統(tǒng)計(jì)答案即可，至此我們得到了\(O(n^2)\)做法。
觀察上述求解過程，我們?cè)趯?duì)\(c\)數(shù)組做區(qū)間修改并訪問整個(gè)\(raw\)數(shù)組區(qū)間和，不難想到，我們可以用線段樹維護(hù)。不同與普通線段樹，我們只需要訪問樹根的值，所以，我們可以省略push_down操作，改為維護(hù)兩個(gè)數(shù)組\(len\)和\(cnt\)，\(cnt[i]\)表示對(duì)于當(dāng)前線段樹節(jié)點(diǎn)的\([l,r]\)被覆蓋了幾次，\(len[i]\)表示，當(dāng)前節(jié)點(diǎn)\([l,r]\)對(duì)于\(h\)的貢獻(xiàn)。顯然，整體的\(h\)就是根節(jié)點(diǎn)的\(len\)，值得注意的是，push_up操作有所不同，如果當(dāng)前節(jié)點(diǎn)的\(cnt>0\),表示當(dāng)前節(jié)點(diǎn)對(duì)應(yīng)的\([l,r]\)被全覆蓋，所以再加上子節(jié)點(diǎn)的貢獻(xiàn)就重復(fù)了，此時(shí)\(len[i]=raw[r+1]-raw[l]\)，否則，就通過子節(jié)點(diǎn)更新。同時(shí)，因?yàn)楦?span id="w0obha2h00" class="math inline">\(len\)值可能是通過子節(jié)點(diǎn)，所以，在該節(jié)點(diǎn)被全部包含也就是\(return\)之前，也要push_up。
最后提醒一句，大部分掃描線需要離散化。
線段樹部分:
#define lx x<<1
#define rx (x<<1)+1
void build(int tl,int tr,int x)
{
l[x]=tl,r[x]=tr;
if(l[x]==r[x]) return;
int mid=(l[x]+r[x])>>1;
build(tl,mid,lx);
build(mid+1,tr,rx);
}
void push_up(int x)
{
if(cnt[x]>0) len[x]=raw[r[x]+1]-raw[l[x]];
else len[x]=len[lx]+len[rx];
}
void modify(int dl,int dr,int x,int d)
{
if(dl<=l[x] && dr>=r[x])
{
cnt[x]+=d;
push_up(x);
return;
}
int mid=(l[x]+r[x])>>1;
if(dl<=mid) modify(dl,dr,lx,d);
if(dr>mid) modify(dl,dr,rx,d);
push_up(x);
}
周長(zhǎng)的并：
定義類比面積并。
我們?cè)诰S護(hù)面積并時(shí)用到了掃描線停頓位置的\(h\)，顯然，這對(duì)于求周長(zhǎng)并是很有幫助的。
先給出結(jié)論：
將四元組按照\(x\)為第一關(guān)鍵字，\(d\)為第二關(guān)鍵字排序后，有：
\(C=\vert \sum_{i=1}^{n}{h_i-h_{i-1}} \rvert+\vert\sum_{i=1}^{n}{w_i-w_{i-1}}\rvert\)（其中\(h\)為橫向掃描的高度，\(w\)為縱向掃描的寬度）
隨便畫幾個(gè)矩形，手模一下就可以發(fā)現(xiàn)\(\vert h_i-h_{i-1}\rvert\)實(shí)際上就是\(h\)增加的長(zhǎng)度，每次加上$ \Delta h$最終一定是周長(zhǎng)左右長(zhǎng)度，橫縱分別掃一遍就是整個(gè)周長(zhǎng)。那為什么還要按照 \(d\) 排序呢？觀察發(fā)現(xiàn)，如果前一個(gè)矩形和后一個(gè)矩形的左邊和右邊重合，實(shí)際上前一個(gè)矩形的右邊是沒有全部作為周長(zhǎng)的，但是由于$ d=1$ 所以，你的代碼會(huì)將它誤認(rèn)為沒有邊覆蓋它了，也就是全部作為周長(zhǎng)的一部分了。這就需要將這個(gè)位置所有覆蓋的邊全部先加上，然后再去判斷是否覆蓋（感性理解一下，不懂的可以用desmos畫圖手玩一下），其他的正常跑兩邊線段樹即可。
模板：P1856 [IOI 1998 / USACO5.5] 矩形周長(zhǎng) Picture
代碼：
#include<bits/stdc++.h>
#define lx x<<1
#define rx (x<<1)+1
#define x1 qqq
#define x2 www
#define y1 eee
#define y2 rrr
using namespace std;
const int N=5e4;
int X[N],Y[N];
struct A
{
int x1,x2;
int y1,y2;
}sq[2*N];
struct B
{
int x;
int yl,yh;
int vl;
} line[2*N];
struct C
{
int y;
int xf,xb;
int vl;
} level[N];
int len[8*N],cnt[8*N],l[8*N],r[8*N];
int mx,my,pos;
int n;
void dis()
{
sort(X+1,X+2*n+1);
mx=unique(X+1,X+2*n+1)-(X+1);
sort(Y+1,Y+2*n+1);
my=unique(Y+1,Y+2*n+1)-(Y+1);
}
int askx(int x)
{
return lower_bound(X+1,X+mx+1,x)-X;
}
int asky(int x)
{
return lower_bound(Y+1,Y+my+1,x)-Y;
}
void build(int tl,int tr,int x)
{
l[x]=tl,r[x]=tr,len[x]=cnt[x]=0;
if(tl==tr) return;
int mid=(l[x]+r[x])>>1;
build(l[x],mid,lx);
build(mid+1,r[x],rx);
}
void push_up(int x,int k)
{
if(k==1)
{
if(cnt[x]) len[x]=X[r[x]+1]-X[l[x]];
else len[x]=len[lx]+len[rx];
}
if(k==2)
{
if(cnt[x]) len[x]=Y[r[x]+1]-Y[l[x]];
else len[x]=len[lx]+len[rx];
}
}
void modify(int dl,int dr,int x,int d,int k)
{
if(dl<=l[x] && dr>=r[x])
{
cnt[x]+=d;
push_up(x,k);
return;
}
int mid=(l[x]+r[x])>>1;
if(dl<=mid)modify(dl,dr,lx,d,k);
if(dr>mid) modify(dl,dr,rx,d,k);
push_up(x,k);
}
bool cmp(B a,B b)
{
if(a.x==b.x) return a.vl>b.vl;
return a.x<b.x;
}
bool cnp(C a,C b)
{
if(a.y==b.y) return a.vl>b.vl;
return a.y<b.y;
}
int main(){
// freopen("text.in","r",stdin);
// freopen("text.out","w",stdout);
cin>>n;
for(int i=1;i<=n;i++)
{
int x1,y1,x2,y2;
cin>>x1>>y1>>x2>>y2;
sq[i]=(A){x1,x2,y1,y2};
X[i]=x1;
X[i+n]=x2;
Y[i]=y1;
Y[i+n]=y2;
}
dis();
for(int i=1;i<=n;i++)
{
int x1=sq[i].x1,x2=sq[i].x2,y1=sq[i].y1,y2=sq[i].y2;
line[++pos]=(B){askx(x1),asky(y1),asky(y2),1};
level[pos]=(C){asky(y1),askx(x1),askx(x2),1};
line[++pos]=(B){askx(x2),asky(y1),asky(y2),-1};
level[pos]=(C){asky(y2),askx(x1),askx(x2),-1};
}
build(1,pos-1,1);
int ans=0,last=0;
sort(line+1,line+pos+1,cmp);
for(int i=1;i<=pos;i++)
{
modify(line[i].yl,line[i].yh-1,1,line[i].vl,2);
int now=len[1];
// cout<<i<<" "<<len[1]<<endl;
ans+=abs(now-last);
last=now;
}
build(1,pos-1,1);
last=0;
sort(level+1,level+pos+1,cnp);
for(int i=1;i<=pos;i++)
{
modify(level[i].xf,level[i].xb-1,1,level[i].vl,1);
int now=len[1];
ans+=abs(now-last);
last=now;
}
cout<<ans;
}
其他：
正如上文所言，掃描線是一種思想，我們可以把一些其他要維護(hù)的東西替換掉\(h\)，運(yùn)用同樣的思路推廣出不同的解法
例題：P1502 窗口的星星
稍微點(diǎn)撥一下：
可以把星星的亮度和作為維護(hù)對(duì)象，把每個(gè)可以至少覆蓋到這顆星星的位置看做一個(gè)矩形。
正解及代碼請(qǐng)參考題解。
結(jié)語：
到這里，掃描線的入門部分就結(jié)束啦，作為一種思想，我們還需要把它運(yùn)用到題目中才可以熟練掌握，另外的，掃描線還可以運(yùn)用到其他坐標(biāo)系問題中，比如二維數(shù)點(diǎn)，B維正交范圍，當(dāng)然，本文為掃描線入門，更高深的內(nèi)容請(qǐng)移步dalao們的博客，等作者學(xué)習(xí)之后也會(huì)更，也許吧。
完結(jié)撒花~
都讀到這里了，如果您覺得本文不錯(cuò)可以給個(gè)贊嗎， rp++。
浙公網(wǎng)安備 33010602011771號(hào)