Mato is No.1

【本沙茶以前曾經(jīng)搞過矩形的面積并、周長并問題，當時幾乎是抄神犇代碼的，根本木有理解，現(xiàn)在在看了掃描線以后理解一些了】
“掃描線”嚴格來說不是算法，而是一種思想，它在解決很多幾何問題或者矩陣問題中有大用。所謂“掃描線”，就是用一條假想的直線（一般是水平或者豎直的）沿x軸（或y軸）方向掃過整個平面，在此過程中，每當發(fā)現(xiàn)有特殊事件（比如插入、刪除事件等），就執(zhí)行這一事件。一般來說，它需要配合數(shù)據(jù)結構進行加速，常用的數(shù)據(jù)結構有線段樹、平衡樹、樹狀數(shù)組、堆、凸多邊形集合等。

【1】矩形的面積并和周長并問題：
這個在以前總結的那一篇里面曾經(jīng)說明過，這里只是補充一下。

對于面積并，可以假想一條水平直線沿y軸正方向掃過整個平面，每當遇到矩形的上下邊界，就插入或刪除一條線段（上邊界為插入，下邊界為刪除），在每兩個相鄰上下邊界之間得到覆蓋面積為：目前插入（尚未刪除）的所有線段覆蓋的總長度乘以兩邊界間的距離。顯然，求前者需要用離散化（橫坐標）+線段樹實現(xiàn)。

這里講一下離散化的步驟和易疵點：首先將要離散化的數(shù)據(jù)（設為A數(shù)組）存儲在一個數(shù)組B里，然后對B排序（一般是遞增排序）、去重（方法：若B長度為0則不需去重，否則B[0]保留，從B[1]開始，若B[i]>B[i-1]則保留B[i]否則跳過B[i]），得到一個新的數(shù)組B0，最后，再對原來的A數(shù)組中的每個元素在B0中二分查找，找到其位置即可。顯然，對N個數(shù)據(jù)離散化時間復雜度為O(NlogN)，具體實現(xiàn)時，可不設B0，直接存在B里面（見代碼）。易疵的地方主要是B的長度為0的情況。 其中n0為數(shù)據(jù)個數(shù)，n為去重后的數(shù)據(jù)個數(shù)（也就是離散化后的編號范圍，很重要的！），find_x為二分查找過程。

對于周長并可以這樣理解：照樣是水平直線沿y軸正方向掃過整個平面，照樣是遇到矩形的上下邊界就插入或刪除，這樣，周長的水平部分是很好得到的，只要統(tǒng)計每兩個相鄰上下邊界的線段覆蓋總長之差即可，對于豎直部分則需要統(tǒng)計被線段覆蓋的端點個數(shù)——或者說，需要統(tǒng)計至少作為一條目前插入線段的端點，且木有被任何一條線段內部包含的端點個數(shù)（因為只有這些點所延伸下來的豎直線段有可能作為周長的豎直部分）。維護方法：給每個結點設立ss、lbd與rbd，分別表示該結點區(qū)間內這種點的個數(shù)，以及該線段區(qū)間的左右端點是不是這種點。lbd=LCH.lbd; rbd=RCH.rbd; ss=LCH.ss+RCH.ss-2*(LCH.rbd || RCH.lbd)（因為我們需要的是線段樹而不是點樹，因此其中的每個葉結點表示的實際上是一條單位線段，而不是一個點，這樣，LCH區(qū)間的右端點與RCH區(qū)間的左端點其實是同一個點，如果它們都是這種點，則都不能算，因為被包含在內部了）。例外的是，如果某個結點區(qū)間完全被某條插入線段包含，則ss為2，lbd、rbd均為1（這個結果可能不正確，因為可能左右端點被包含在內部，因此，整棵樹上只有根結點的ss值是絕對正確的ss值，其余結點都需要特判）。這樣，根結點的ss值就是這種點的個數(shù)，乘以兩相鄰上下邊界的距離就是之間的豎直部分總長度。

代碼：
面積并（HDU1542）
周長并（HDU1828）

（此外，周長并還有一種更容易理解的算法：就是先求出水平部分總長后，將所有的矩形旋轉90度，再求一次水平部分總長，這就是原來的豎直部分總長了）

【2】應用：
PKU2482