原題地址
這是一道線段樹操作的極品題，因為它的4個操作剛好覆蓋了線段樹操作問題的3種處理思路，可以說是把線段樹操作的全部內(nèi)容都包含進去了。

線段樹是一種靜態(tài)的數(shù)據(jù)結(jié)構，因為一棵線段樹一旦建成，其形態(tài)就永遠不會發(fā)生變化，改變的僅僅是結(jié)點上記錄的各種信息的值。因此，對于線段樹操作，核心問題也就是如何維護和處理這些信息。總的來說，對于線段樹結(jié)點信息的維護和處理，有以下3種基本思路：
（1）左右歸中型：
所謂左右歸中，就是用左右子結(jié)點存儲的信息來得到父結(jié)點存儲的信息的值，這是最常見的線段樹維護方法。舉一些簡單的例子：比如結(jié)點的SUM域表示該結(jié)點區(qū)間上所有元素的和，那么這個域維護的方法就是“父結(jié)點SUM=左子結(jié)點SUM+右子結(jié)點SUM”，再比如結(jié)點的MAX/MIN域表示該結(jié)點區(qū)間上所有元素的最大/小值，那么維護方法就是“父結(jié)點MAX/MIN=max/min{左子結(jié)點MAX/MIN,右子結(jié)點MAX/MIN}”。這種維護方法也比較簡單，只要在每次對子結(jié)點進行修改之后upd一下就行了（對于那些自頂向下遞歸，而且涉及到改值的操作，在遞歸完左右子結(jié)點后一定要記得upd一下），在這之中有一個很重要的思想就是“左右連續(xù)段”思想：如果題目中要求任意一個區(qū)間內(nèi)的具有某種性質(zhì)的最長的連續(xù)序列（也就是子區(qū)間），比如最長連續(xù)上升子序列、01值問題中連續(xù)的0段或者非0段（在具體問題中就是連續(xù)的空閑段或者占用段）等，可以在每個結(jié)點上維護三個域：lS、rS和S，分別表示該結(jié)點區(qū)間左端（從區(qū)間的最左端開始的）具有這種性質(zhì)的最長連續(xù)序列的長度，該結(jié)點區(qū)間右端（到區(qū)間的最右端結(jié)束的）具有這種性質(zhì)的最長連續(xù)序列的長度和該區(qū)間內(nèi)具有這種性質(zhì)的最長連續(xù)序列的長度（也就是要求的那個東東），則維護方法為“父結(jié)點lS=左子結(jié)點lS（左子結(jié)點lS<左子結(jié)點len）或左子結(jié)點len+右子結(jié)點lS（左子結(jié)點lS=左子結(jié)點len），父結(jié)點rS類似，父結(jié)點S=max{左子結(jié)點S,右子結(jié)點S,左子結(jié)點rS+右子結(jié)點lS}”，此外，由于要求的這個區(qū)間可能被拆成多個連續(xù)的結(jié)點區(qū)間，因此需要按順序合并這些區(qū)間，合并的方法是：設立S0和S1，S0表示不保證能延伸下去的區(qū)間長度，S0=上一個區(qū)間的S1+本區(qū)間的lS；S1表示可以延伸下去的區(qū)間長度，S1=上一個區(qū)間的S1+本區(qū)間len（如果本區(qū)間整個都是滿足條件的，即S=len）或本區(qū)間的rS（本區(qū)間不都是滿足條件的，即S<len），取過程中所有S0和區(qū)間S的最大值即為結(jié)果。
在HDU2871中，應用左右歸中的方法維護的信息就是“最長連續(xù)空閑段”的長度，New操作需要；

（2）調(diào)整邊界型：
考慮這樣一個問題：現(xiàn)在要插入、刪除一些[0, 100000)的整數(shù)，并且在此過程中不斷詢問第K小的整數(shù)是多少，怎么辦？平衡樹可以實現(xiàn)，但線段樹顯然是更好的方法。對每個結(jié)點，存儲一個K0值表示位于該結(jié)點區(qū)間內(nèi)的整數(shù)的個數(shù)，則查找第K小的時候只需要不斷執(zhí)行以下操作：Kth(A, K)，表示在結(jié)點A代表的區(qū)間內(nèi)找第K小的，然后，若K<=結(jié)點A的左子結(jié)點K0值，則執(zhí)行Kth(A的左子結(jié)點, K)，否則執(zhí)行Kth(A的右子結(jié)點, K-A左子結(jié)點的K0)（這和平衡樹神似），直到找到葉結(jié)點為止。這種方法稱為“調(diào)整邊界型”，即隨著結(jié)點深入，不斷縮小（自頂向下）或擴大（自底向上）范圍，最后找到結(jié)果。像找第K小這樣的操作屬于自頂向下型，而像“找到X所在的具有某種性質(zhì)的最長的連續(xù)區(qū)間”就屬于自底向上型（注意和本題的Free不一樣）；

（3）標記輔助型：
這種維護信息的方法，特點是利用標記來維護信息，即對于某些結(jié)點（主要是葉結(jié)點，因為其標記不再下放），直接使用標記來得到一些數(shù)據(jù)，比如對于HDU2871這一題，其中對于葉結(jié)點位于的插入線段的標號，使用的就是標記。

下面是本題4個操作的具體實現(xiàn)：
<1>線段樹結(jié)點定義：
本題需要兩棵線段樹，這是因為New與Free操作對于tot域（插入線段左端點的總個數(shù)）會造成不同的影響，具體來說，在New操作中，tot值不會被同時加上（需要另外一個操作加上），然而在Free操作中，tot值會被同時清空，這樣就會導致在對某個結(jié)點清空（該結(jié)點包含在某個Free操作要清空的線段中）并打上0標記之后，如果緊接著又插入一條包含這個結(jié)點區(qū)間的新線段，則這個結(jié)點的0標記就會喪失，這樣在緊接著下傳的時候，其子結(jié)點的tot值就不會被清空（事實上已經(jīng)被清空了）。所以，將tot域徹底轉(zhuǎn)移到另一棵線段樹里。 其中l(wèi)sc、rsc、sc就是連續(xù)空閑段的長度（用左右歸中的方法維護），mr是一個整體賦值標記，在T中，mr的值若為-1表示無標記（未被整體賦值），若為0表示被整體清空，若大于0表示整體被一條線段覆蓋，mr值就是這條線段的編號（為區(qū)分不同線段，這里按照輸入順序?qū)γ恳粭lNew操作插入的線段以1、2……編號），在T0中，mr=1表示在Reset中被整體清空，mr=0表示無標記。
<2>操作處理：
1)Reset操作：將T、T0的根結(jié)點打上清空標記即可；
2)New：涉及到兩個操作，分別是找最左的長度為x的連續(xù)空閑段，以及插入一條線段。對于前者，可以根據(jù)lsc、rsc、sc的值，按照“先左子結(jié)點，再跨越兩個子結(jié)點，最后右子結(jié)點”的順序求得（詳見代碼）；對于后者就不用說了，太容易實現(xiàn)了（注意標記的處理以及upd，另外要插入一個tot）；
3)Free：也涉及兩個操作，分別是找一個點x所在的線段（插入過的線段）長度以及刪除一條線段，對于前者可將New插入過的所有線段的左右端點預存起來，然后找到代表區(qū)間[x, x]的結(jié)點的mr值（也就是結(jié)點x被編號為神馬的線段覆蓋），再在預存的線段中找到即可。對于后者，直接清空即可（不要在T0中打標記，而要單獨刪除一個tot）；
4)Get：直接利用T0中的tot找到第K小的值即可；

代碼