國家集訓(xùn)隊2004論文集 林濤

《國家集訓(xùn)隊2004論文集 林濤》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在教育資源-天天文庫。

1、線段樹的應(yīng)用廣西柳鐵一中林濤線段樹的定義線段樹是一棵二叉樹，記為T(a,b)，參數(shù)a,b表示區(qū)間[a,b]，其中b-a稱為區(qū)間的長度，記為L。線段樹T(a,b)也可遞歸定義為：若L>1:[a,(a+b)div2]為T的左兒子；[(a+b)div2,b]為T的右兒子。若L=1:T為葉子節(jié)點。表示區(qū)間[1,10]的線段樹樣例：[1,10][1,5][5,10][1,3][3,5][5,7][7,10][1,2][2,3][3,4][4,5][5,6][6,7][7,8][8,10][8,9][9,10]

2、線段樹的特征定理二：線段樹把區(qū)間上的任意一條線段都分成不超過2logL條線段。這些結(jié)論為線段樹能在O(logL)的時間內(nèi)完成一條線段的插入、刪除、查找等工作，提供了理論依據(jù)定理一：線段樹的深度不超過logL。線段樹的基本操作插入一條線段：每個節(jié)點增加一個變量記錄該節(jié)點被插入所有線段覆蓋的次數(shù)，自根節(jié)點往下，直到一個被線段完全覆蓋的節(jié)點。節(jié)點被插入的線段覆蓋記錄變量加1，兒子不再處理節(jié)點與插入線段不相干該節(jié)點及兒子都不作處理相干但不被覆蓋把線段分別插入它的兩個兒子刪除一條插入過的線段，與插入操作是一致

3、的。查找一個區(qū)間內(nèi)線段的總長度。每個節(jié)點增加一個變量記錄該區(qū)間內(nèi)線段的總長度，并在插入和刪除后維護相關(guān)節(jié)點的這個變量：兒子區(qū)間內(nèi)的線段長度+覆蓋本區(qū)間的線段長度例1：蛇（SGU128）在平面上有N個點，現(xiàn)在要用一些線段將它們連起來，使其滿足以下要求：1這些線段必須閉合2線段的端點只能是這N個點。3交于一點的兩條線段成90度角4線段都必須平行于X軸或Y軸5所有線段除了在這N個點外不相交6所有線段的長度之和必須最短如果存在這樣的線段，則輸出最小長度，否則輸出0。XY【問題分析】所求的圖形是以題目所給的N

4、個點為頂點的多邊形。每條邊要和X軸或Y軸平行。每個頂點與一條平行于X軸和一條平行于Y軸的線段相連。XYP1P2P3P4P5P6P7P8P1P2P3P4P5P6將所有點排序后發(fā)現(xiàn)，在同一水平線的點中，設(shè)為P1，P2，P3，P4……Pn，P1必須連它右邊的點——P2，P3只能連P4，P5連P6……，同垂直線上的點也是如此。如果有解，解是唯一的，那么最小長度的問題就解決了。不相連—不合法不自交—合法自交—不合法由于解是唯一，所以關(guān)鍵在于判斷由上述方法構(gòu)出的圖形是否合法——滿足線段不自交：【問題分析】如圖，

5、兩條線段在內(nèi)部相交，則必須滿足x1

6、點數(shù)。按順序，掃描所有事件：如果遇到平行于X軸線段的左端點，則插入到線段樹中，遇到右端點，則從線段樹中刪除。如果遇到平行于Y軸的線段，則在線段樹中查找。S1S2S3S4將Ｙ軸坐標離散后，每次插入、刪除、查找的復(fù)雜度是Ｏ(logn)級別的，由于所有線段數(shù)量是Ｏ(n)級別的，所以整題的復(fù)雜度是Ｏ(nlogn)級別。思考：本題刪除的點與插入的點一一對應(yīng)，所以刪除實現(xiàn)很方便。如果刪除的線段不一定插入過該怎么辦？例2：空心長方體（POI99Cuboid）在一個三維正坐標系中，存在N(N<=5000)個點，現(xiàn)在

7、要求一點P(x，y，z)，使得O(0，0，0)與P(x，y，z)兩個頂點構(gòu)成的長方體內(nèi)不包括N個點中的任何一個點(在長方體邊緣不算包括)，并使這個長方體的體積最大。x，y，z均不得超過1000000?！締栴}分析】P(x,y,z)代表的長方體包含一點Q，那么P的所有坐標值，都大于Q點的坐標值。Px>QxPy>QyPz>Qz體積最大的長方體，其P點任意軸的坐標，都與N個點中的一個相同或者和邊界相同?！締栴}分析】在已經(jīng)確定P的X坐標情況下,將所有點的y坐標排序，得到序列y[1]，y[2]，y[3]……。m

8、ax[i]記錄P的Y軸坐標為y[i]時，Z軸坐標的最大取值，數(shù)組max的值是單調(diào)不增的。把所有點按X軸坐標排序，當(dāng)P點的X坐標與第i個點相同時，第i及第i以后的點都不可能被P包含了。y[i]>Qy把max看成一個區(qū)間y[i]>Qymax[j]>z可以看出每增加一個點的限制，需要修改的是一個區(qū)間，要高效的進行區(qū)間操作就可以用到線段樹?！締栴}分析】從小到大枚舉P點的X坐標，這個過程中要不斷維護數(shù)組max。因為P的X坐標由第i個點的變成第i+1個點的，第i個點的坐標就會增加