矩形的面積并問(wèn)題：平面上有N個(gè)矩形，各邊均平行于坐標(biāo)軸，求它們覆蓋的總面積（重復(fù)覆蓋的只計(jì)一次）。
矩形的周長(zhǎng)并問(wèn)題：平面上有N個(gè)矩形，各邊均平行于坐標(biāo)軸，求它們覆蓋形成的多邊形的周長(zhǎng)。

【算法】
面積并：
先將所有矩形的上邊界和下邊界作為水平線段記錄下來(lái)，并對(duì)所有矩形的左右邊界對(duì)應(yīng)的橫坐標(biāo)離散化，設(shè)離散化后有N個(gè)橫坐標(biāo)，則中間有(N-1)段。對(duì)這(N-1)段建立線段樹（注意，仍然和普通線段樹一樣，是雙閉區(qū)間，不是網(wǎng)上說(shuō)的一開一閉），然后，按照縱坐標(biāo)遞增順序掃描前面記錄的水平線段（設(shè)有M段），對(duì)每一段，如果是上邊界，找到其離散化后的范圍（只需找到其左右端點(diǎn)離散化后的值l、r，則對(duì)應(yīng)范圍為[l, r-1]），并插入線段[l, r-1]，否則（下邊界），刪除線段[l, r-1]。再然后，線段樹中的每個(gè)結(jié)點(diǎn)需要記錄該區(qū)間內(nèi)的線段覆蓋的總長(zhǎng)度len（若該區(qū)間被某條尚未刪除的線段整體覆蓋，則len=總長(zhǎng)，否則len=左右子結(jié)點(diǎn)len之和），每次操作后，累加面積：T[root].len*該水平線段與下一條水平線段的縱坐標(biāo)之差。

周長(zhǎng)并：
類似，只不過(guò)由于組成周長(zhǎng)的線段有水平的也有豎直的，線段樹結(jié)點(diǎn)要記錄的除了len意外還有一個(gè)ss，表示被線段覆蓋的端點(diǎn)數(shù)量。另外還有l(wèi)r和rr兩個(gè)bool值，分別表示該線段的左端點(diǎn)和右端點(diǎn)是否被某條插入的線段覆蓋。則T[x].ss = lch(T[x]).ss + rch(T[x]).ss - 2 * (lch(T[x]).rr && rch(T[x].lr))，若該線段被整體覆蓋則T[x].ss=2（兩端點(diǎn)）。最后，這次得到的T[root].len與上次得到的T[root].len之差的絕對(duì)值就是水平線段的長(zhǎng)度，T[root].ss*縱坐標(biāo)之差就是豎直線段的長(zhǎng)度。