Posted on 2011-07-02 11:17
Mato_No1 閱讀(2775)
評論(0) 編輯 收藏 引用 所屬分類:
線段樹
矩形的面積并問題：平面上有N個矩形，各邊均平行于坐標軸，求它們覆蓋的總面積（重復覆蓋的只計一次）。
矩形的周長并問題：平面上有N個矩形，各邊均平行于坐標軸，求它們覆蓋形成的多邊形的周長。
【算法】
面積并：
先將所有矩形的上邊界和下邊界作為水平線段記錄下來，并對所有矩形的左右邊界對應的橫坐標離散化，設離散化后有N個橫坐標，則中間有(N-1)段。對這(N-1)段建立線段樹（注意，仍然和普通線段樹一樣，是雙閉區間，不是網上說的一開一閉），然后，按照縱坐標遞增順序掃描前面記錄的水平線段（設有M段），對每一段，如果是上邊界，找到其離散化后的范圍（只需找到其左右端點離散化后的值l、r，則對應范圍為[l, r-1]），并插入線段[l, r-1]，否則（下邊界），刪除線段[l, r-1]。再然后，線段樹中的每個結點需要記錄該區間內的線段覆蓋的總長度len（若該區間被某條尚未刪除的線段整體覆蓋，則len=總長，否則len=左右子結點len之和），每次操作后，累加面積：T[root].len*該水平線段與下一條水平線段的縱坐標之差。
周長并：
類似，只不過由于組成周長的線段有水平的也有豎直的，線段樹結點要記錄的除了len意外還有一個ss，表示被線段覆蓋的端點數量。另外還有lr和rr兩個bool值，分別表示該線段的左端點和右端點是否被某條插入的線段覆蓋。則T[x].ss = lch(T[x]).ss + rch(T[x]).ss - 2 * (lch(T[x]).rr && rch(T[x].lr))，若該線段被整體覆蓋則T[x].ss=2（兩端點）。最后，這次得到的T[root].len與上次得到的T[root].len之差的絕對值就是水平線段的長度，T[root].ss*縱坐標之差就是豎直線段的長度。