掃描線：
下面是來自soar轉載的一篇部落格。
這篇部落格解決了我對算區間長度時的不了解。實際上這個線段樹的葉子節點儲存的是這個點x坐标到下一個x坐标（排序後的）的區間長度。
題意:
二維平面有n個平行于坐标軸的矩形,現在要求出這些矩形的總面積. 重疊部分隻能算一次.
分析:
線段樹的典型掃描線用法.
首先假設有下圖兩個矩陣,我們如果用掃描線的方法如何計算它們的總面積呢?
首先我們将矩形的上下邊分為上位邊(即y坐标大的那條平行于x軸的邊),和下位邊(y坐标小的平行于x軸的邊).然後我們把所有矩形的上下位邊按照他們y坐标從小到大排序,可以得到4條掃描線:
又因為上面2個矩形有4個不同的浮點數x坐标,是以我們需要把x坐标離散化,這樣才能用線段樹來維護資訊.是以我們這樣離散化:
由上圖可知,4個不同的x坐标把x軸分成了3段有效的區間.這裡要注意我們線段樹中每個葉節點(控制區間[L,L])不是指X[L]坐标,而是指區間[X[L],X[L+1]].線段樹中其他節點控制的區間[L,R],也是指的x坐标軸的第L個區間到第R個區間的範圍,也就是X[L]到X[R+1]坐标的範圍.
然後我們Y坐标從小到大的順序讀入每條掃描線,并維護目前我們所讀入的所有掃描線能有效覆寫X軸的最大長度sum[1].這裡特别要注意如果我們讀入的掃描線是矩形的下位邊,那麼我們就使得該範圍的标記cnt位+1,如果是上位邊,那麼該範圍的cnt就-1.是以如果cnt=0時,表示該節點控制的範圍沒有被覆寫,隻要cnt!=0 就表示該節點控制的幾塊區間仍然被覆寫.
下面依次讀入每條矩陣邊,來一一分析,首先是讀入第一條矩陣邊:
我們讀入了矩形1的下位邊,那麼該區域的cnt就+1=1了,是以該區域[10,20]就被覆寫了,然後可以推出整個區域被覆寫的長度是10.再根據第二條掃描線離第一條掃描線的高度差為5.是以不管你第二條掃描線是哪個矩形的什麼邊,或者能覆寫到X軸的什麼範圍,我上圖中藍色的矩形面積肯定是要算到總面積裡面去的.即總面積ret+=sum[1]*(掃描線2的高度-掃描線1的高度). (想想看是不是這樣).
下面讀第二條掃描線:
由于第二條掃描線也是下位邊,是以[15,20]和[20,25]的cnt+1.使得我們覆寫的範圍變成了[10,25]了,并且第3條掃描線在20高度,是以這次我們必然增加的面積是上面深藍色的長條=sum[1]*(掃描線3的高度-掃描線2的高度).
下面我們要讀第三條掃描線了:
由于第三條掃描線是區間[10,20]的上位邊,是以對應區間的cnt要-1,是以使得區間[10,15]的cnt=0了,而[15,20]區間的cnt-1之後變成了1.[20,25]的cnt仍然為1,不變.是以目前覆寫的有效x軸長度為10,即區間[15,25].是以增加的面積是圖中褐色的部分.
到此,矩形的面積和就算出來了.由于對于任一矩形都是先讀下位邊(cnt+1),再讀上位邊(cnt-1)的,是以在更新線段樹的過程中,任意節點的cnt都是>=0的.
下面說代碼實作部分:
首先建立一個node結構體用來儲存每條掃描線,node中有資訊:
l: 表示掃描線的左端x坐标
r:表示掃描線的右端x坐标
h: 表示掃描線的高度
d: 為1或-1,标記掃描線是矩形的上位還是下位邊.
我們首先讀入所有矩形的資訊,每讀入一個矩形資訊我們就更新兩條掃描線,并且把矩形的兩個端點x坐标放入X[MAXN]數組中,
然後我們對node和X都排序,node按h值從小到大排序.
X按從小到大排序.
然後我們在X的本地數組内,對X去重,并且用k表示一共有多少個X.
當我們需要找到第i個區域的兩端點坐标時,隻需要X[i]和X]i+1].
線段樹維護cnt(根本資訊)和sum兩個資訊,其中sum為double,cnt為int型.
cnt: >=0時表示本節點控制的區域内下位邊個數-上位邊個數的結果.如果==-1時,表示本節點左右子樹的上下位邊數不一緻.
sum: 本節點控制的區域内cnt值不為0的區域總長度.
線段樹操作:
PushDown(i,l,r):如果cnt!=-1,那麼下放cnt資訊,并更新子節點的sum資訊.
PushUp(i,l,r): 根據子節點的cnt值和sum值更新父節點的cnt和sum值.
update(ql,qr,v,i,l,r): 使得[ql,qr]與[l,r]區間的公共部分cnt值+v.
如果ql<=l && r<=qr 且 cnt[i]!=-1的話,直接更新并return
否則先PushDown
在一次遞歸更新左右兒子
最後PushUp.
首先我們将矩形的上下邊分為上位邊(即y坐标大的那條平行于x軸的邊),和下位邊(y坐标小的平行于x軸的邊).然後我們把所有矩形的上下位邊按照他們y坐标從小到大排序,可以得到4條掃描線:
又因為上面2個矩形有4個不同的浮點數x坐标,是以我們需要把x坐标離散化,這樣才能用線段樹來維護資訊.是以我們這樣離散化:
由上圖可知,4個不同的x坐标把x軸分成了3段有效的區間.這裡要注意我們線段樹中每個葉節點(控制區間[L,L])不是指X[L]坐标,而是指區間[X[L],X[L+1]].線段樹中其他節點控制的區間[L,R],也是指的x坐标軸的第L個區間到第R個區間的範圍,也就是X[L]到X[R+1]坐标的範圍.
我們讀入了矩形1的下位邊,那麼該區域的cnt就+1=1了,是以該區域[10,20]就被覆寫了,然後可以推出整個區域被覆寫的長度是10.再根據第二條掃描線離第一條掃描線的高度差為5.是以不管你第二條掃描線是哪個矩形的什麼邊,或者能覆寫到X軸的什麼範圍,我上圖中藍色的矩形面積肯定是要算到總面積裡面去的.即總面積ret+=sum[1]*(掃描線2的高度-掃描線1的高度). (想想看是不是這樣).
由于第二條掃描線也是下位邊,是以[15,20]和[20,25]的cnt+1.使得我們覆寫的範圍變成了[10,25]了,并且第3條掃描線在20高度,是以這次我們必然增加的面積是上面深藍色的長條=sum[1]*(掃描線3的高度-掃描線2的高度).
由于第三條掃描線是區間[10,20]的上位邊,是以對應區間的cnt要-1,是以使得區間[10,15]的cnt=0了,而[15,20]區間的cnt-1之後變成了1.[20,25]的cnt仍然為1,不變.是以目前覆寫的有效x軸長度為10,即區間[15,25].是以增加的面積是圖中褐色的部分.
下面說代碼實作部分:
在一次遞歸更新左右兒子