Posted on 2012-11-25 14:54
Mato_No1 閱讀(652)
評論(0) 編輯 收藏 引用 所屬分類:
線段樹 、
平衡樹 、
專題:數據結構動態模擬問題
原題地址本沙茶去年曾經用雙線段樹的方法捉了這題（詳見
這里），最近重新審視這題發現，借助平衡樹，可以得到更簡單的方法。
題目大意：
有一個長度為N的內存條，每個位置的狀態有占用和不占用兩種，有4種操作：
（1）Reset：清空所有內存（即將所有位置的狀態改為不占用，刪除所有內存塊）；
（2）New x：申請一個新的內存塊，即找到一個長度為x的連續不占用位置區間，將它們標記為占用，若有多個這樣的區間，取最左邊的，若木有輸出Reject New；
（3）Free x：在已申請的內存塊中，找到包含位置x的并釋放（將該內存塊刪除，同時其占用的所有位置改為不占用），若木有內存塊包含位置x，則輸出Reject Free；
（4）Get x：找出已申請的內存塊中，左起第x個，并輸出其左端點；若已申請的內存塊數目不足x個，則輸出Reject Get。
可以發現，每個已經申請的內存塊盡管代表一段區間，但仍然是獨立的單位，因此，可以把內存塊當成結點，用平衡樹維護（關鍵字為內存塊的左端點位置），New操作中內存塊的插入與Free操作中內存塊的刪除均在此平衡樹內進行，Reset操作只需要將整棵樹銷毀即可。
問題是，在New操作中，需要找到一個長度為x的連續不占用區間，而連續的不占用區間并不是獨立的單位，因此需要使用線段樹維護。在線段樹中，需要維護<1>結點區間內最長連續不占用塊的長度；<2>結點區間左端、右端連續不占用塊的長度（否則無法維護<1>）；同時，由于在New操作中需要區間整體改占用，Free操作中又需要區間整體改不占用，所以應當支持整體改值的標記，對于Reset操作，只需要全部位置改不占用即可（不能重新建樹！！）；
這樣，利用一棵平衡樹加一棵線段樹，就可以得到一個很簡單的方法了（代碼量是雙平衡樹或雙線段樹的一半左右）；
這題的啟示是，在解決數據結構統計類題的時候，到底選用什么樣的數據結構，是有講究的，因為它將直接影響到編程復雜度。一般來說，線段樹比平衡樹好寫，但是對本題而言，雙線段樹反而不如平衡樹加線段樹好寫，這是因為對于內存塊使用平衡樹維護比使用線段樹維護更好。在以后做這種題的時候，要多想一下，找到簡便方法。