原題地址
本沙茶去年曾經(jīng)用雙線段樹的方法捉了這題（詳見這里），最近重新審視這題發(fā)現(xiàn)，借助平衡樹，可以得到更簡單的方法。

題目大意：
有一個長度為N的內(nèi)存條，每個位置的狀態(tài)有占用和不占用兩種，有4種操作：
（1）Reset：清空所有內(nèi)存（即將所有位置的狀態(tài)改為不占用，刪除所有內(nèi)存塊）；
（2）New x：申請一個新的內(nèi)存塊，即找到一個長度為x的連續(xù)不占用位置區(qū)間，將它們標(biāo)記為占用，若有多個這樣的區(qū)間，取最左邊的，若木有輸出Reject New；
（3）Free x：在已申請的內(nèi)存塊中，找到包含位置x的并釋放（將該內(nèi)存塊刪除，同時其占用的所有位置改為不占用），若木有內(nèi)存塊包含位置x，則輸出Reject Free；
（4）Get x：找出已申請的內(nèi)存塊中，左起第x個，并輸出其左端點；若已申請的內(nèi)存塊數(shù)目不足x個，則輸出Reject Get。

可以發(fā)現(xiàn)，每個已經(jīng)申請的內(nèi)存塊盡管代表一段區(qū)間，但仍然是獨立的單位，因此，可以把內(nèi)存塊當(dāng)成結(jié)點，用平衡樹維護(hù)（關(guān)鍵字為內(nèi)存塊的左端點位置），New操作中內(nèi)存塊的插入與Free操作中內(nèi)存塊的刪除均在此平衡樹內(nèi)進(jìn)行，Reset操作只需要將整棵樹銷毀即可。
問題是，在New操作中，需要找到一個長度為x的連續(xù)不占用區(qū)間，而連續(xù)的不占用區(qū)間并不是獨立的單位，因此需要使用線段樹維護(hù)。在線段樹中，需要維護(hù)<1>結(jié)點區(qū)間內(nèi)最長連續(xù)不占用塊的長度；<2>結(jié)點區(qū)間左端、右端連續(xù)不占用塊的長度（否則無法維護(hù)<1>）；同時，由于在New操作中需要區(qū)間整體改占用，F(xiàn)ree操作中又需要區(qū)間整體改不占用，所以應(yīng)當(dāng)支持整體改值的標(biāo)記，對于Reset操作，只需要全部位置改不占用即可（不能重新建樹！！）；

這樣，利用一棵平衡樹加一棵線段樹，就可以得到一個很簡單的方法了（代碼量是雙平衡樹或雙線段樹的一半左右）；

這題的啟示是，在解決數(shù)據(jù)結(jié)構(gòu)統(tǒng)計類題的時候，到底選用什么樣的數(shù)據(jù)結(jié)構(gòu)，是有講究的，因為它將直接影響到編程復(fù)雜度。一般來說，線段樹比平衡樹好寫，但是對本題而言，雙線段樹反而不如平衡樹加線段樹好寫，這是因為對于內(nèi)存塊使用平衡樹維護(hù)比使用線段樹維護(hù)更好。在以后做這種題的時候，要多想一下，找到簡便方法。