原題地址本沙茶去年曾經(jīng)用雙線段樹的方法捉了這題（詳見
這里），最近重新審視這題發(fā)現(xiàn)，借助平衡樹，可以得到更簡單的方法。
題目大意：
有一個(gè)長度為N的內(nèi)存條，每個(gè)位置的狀態(tài)有占用和不占用兩種，有4種操作：
（1）Reset：清空所有內(nèi)存（即將所有位置的狀態(tài)改為不占用，刪除所有內(nèi)存塊）；
（2）New x：申請一個(gè)新的內(nèi)存塊，即找到一個(gè)長度為x的連續(xù)不占用位置區(qū)間，將它們標(biāo)記為占用，若有多個(gè)這樣的區(qū)間，取最左邊的，若木有輸出Reject New；
（3）Free x：在已申請的內(nèi)存塊中，找到包含位置x的并釋放（將該內(nèi)存塊刪除，同時(shí)其占用的所有位置改為不占用），若木有內(nèi)存塊包含位置x，則輸出Reject Free；
（4）Get x：找出已申請的內(nèi)存塊中，左起第x個(gè)，并輸出其左端點(diǎn)；若已申請的內(nèi)存塊數(shù)目不足x個(gè)，則輸出Reject Get。
可以發(fā)現(xiàn)，每個(gè)已經(jīng)申請的內(nèi)存塊盡管代表一段區(qū)間，但仍然是獨(dú)立的單位，因此，可以把內(nèi)存塊當(dāng)成結(jié)點(diǎn)，用平衡樹維護(hù)（關(guān)鍵字為內(nèi)存塊的左端點(diǎn)位置），New操作中內(nèi)存塊的插入與Free操作中內(nèi)存塊的刪除均在此平衡樹內(nèi)進(jìn)行，Reset操作只需要將整棵樹銷毀即可。
問題是，在New操作中，需要找到一個(gè)長度為x的連續(xù)不占用區(qū)間，而連續(xù)的不占用區(qū)間并不是獨(dú)立的單位，因此需要使用線段樹維護(hù)。在線段樹中，需要維護(hù)<1>結(jié)點(diǎn)區(qū)間內(nèi)最長連續(xù)不占用塊的長度；<2>結(jié)點(diǎn)區(qū)間左端、右端連續(xù)不占用塊的長度（否則無法維護(hù)<1>）；同時(shí)，由于在New操作中需要區(qū)間整體改占用，F(xiàn)ree操作中又需要區(qū)間整體改不占用，所以應(yīng)當(dāng)支持整體改值的標(biāo)記，對于Reset操作，只需要全部位置改不占用即可（不能重新建樹！！）；
這樣，利用一棵平衡樹加一棵線段樹，就可以得到一個(gè)很簡單的方法了（代碼量是雙平衡樹或雙線段樹的一半左右）；
這題的啟示是，在解決數(shù)據(jù)結(jié)構(gòu)統(tǒng)計(jì)類題的時(shí)候，到底選用什么樣的數(shù)據(jù)結(jié)構(gòu)，是有講究的，因?yàn)樗鼘⒅苯佑绊懙骄幊虖?fù)雜度。一般來說，線段樹比平衡樹好寫，但是對本題而言，雙線段樹反而不如平衡樹加線段樹好寫，這是因?yàn)閷τ趦?nèi)存塊使用平衡樹維護(hù)比使用線段樹維護(hù)更好。在以后做這種題的時(shí)候，要多想一下，找到簡便方法。