原題地址這是一道線段樹操作的極品題，因為它的4個操作剛好覆蓋了線段樹操作問題的3種處理思路，可以說是把線段樹操作的全部內容都包含進去了。
線段樹是一種靜態的數據結構，因為一棵線段樹一旦建成，其形態就永遠不會發生變化，改變的僅僅是結點上記錄的各種信息的值。因此，對于線段樹操作，核心問題也就是如何維護和處理這些信息。總的來說，對于線段樹結點信息的維護和處理，有以下3種基本思路：
（1）左右歸中型：
所謂左右歸中，就是用左右子結點存儲的信息來得到父結點存儲的信息的值，這是最常見的線段樹維護方法。舉一些簡單的例子：比如結點的SUM域表示該結點區間上所有元素的和，那么這個域維護的方法就是“父結點SUM=左子結點SUM+右子結點SUM”，再比如結點的MAX/MIN域表示該結點區間上所有元素的最大/小值，那么維護方法就是“父結點MAX/MIN=max/min{左子結點MAX/MIN,右子結點MAX/MIN}”。這種維護方法也比較簡單，只要在每次對子結點進行修改之后upd一下就行了（對于那些自頂向下遞歸，而且涉及到改值的操作，在遞歸完左右子結點后一定要記得upd一下），在這之中有一個很重要的思想就是“左右連續段”思想：如果題目中要求任意一個區間內的具有某種性質的最長的連續序列（也就是子區間），比如最長連續上升子序列、01值問題中連續的0段或者非0段（在具體問題中就是連續的空閑段或者占用段）等，可以在每個結點上維護三個域：lS、rS和S，分別表示該結點區間左端（從區間的最左端開始的）具有這種性質的最長連續序列的長度，該結點區間右端（到區間的最右端結束的）具有這種性質的最長連續序列的長度和該區間內具有這種性質的最長連續序列的長度（也就是要求的那個東東），則維護方法為“父結點lS=左子結點lS（左子結點lS<左子結點len）或左子結點len+右子結點lS（左子結點lS=左子結點len），父結點rS類似，父結點S=max{左子結點S,右子結點S,左子結點rS+右子結點lS}”，此外，由于要求的這個區間可能被拆成多個連續的結點區間，因此需要按順序合并這些區間，合并的方法是：設立S0和S1，S0表示不保證能延伸下去的區間長度，S0=上一個區間的S1+本區間的lS；S1表示可以延伸下去的區間長度，S1=上一個區間的S1+本區間len（如果本區間整個都是滿足條件的，即S=len）或本區間的rS（本區間不都是滿足條件的，即S<len），取過程中所有S0和區間S的最大值即為結果。
在HDU2871中，應用左右歸中的方法維護的信息就是“最長連續空閑段”的長度，New操作需要；
（2）調整邊界型：
考慮這樣一個問題：現在要插入、刪除一些[0, 100000)的整數，并且在此過程中不斷詢問第K小的整數是多少，怎么辦？平衡樹可以實現，但線段樹顯然是更好的方法。對每個結點，存儲一個K0值表示位于該結點區間內的整數的個數，則查找第K小的時候只需要不斷執行以下操作：Kth(A, K)，表示在結點A代表的區間內找第K小的，然后，若K<=結點A的左子結點K0值，則執行Kth(A的左子結點, K)，否則執行Kth(A的右子結點, K-A左子結點的K0)（這和平衡樹神似），直到找到葉結點為止。這種方法稱為“調整邊界型”，即隨著結點深入，不斷縮小（自頂向下）或擴大（自底向上）范圍，最后找到結果。像找第K小這樣的操作屬于自頂向下型，而像“找到X所在的具有某種性質的最長的連續區間”就屬于自底向上型（注意和本題的Free不一樣）；
（3）標記輔助型：
這種維護信息的方法，特點是利用標記來維護信息，即對于某些結點（主要是葉結點，因為其標記不再下放），直接使用標記來得到一些數據，比如對于HDU2871這一題，其中對于葉結點位于的插入線段的標號，使用的就是標記。
下面是本題4個操作的具體實現：
<1>線段樹結點定義：
本題需要兩棵線段樹，這是因為New與Free操作對于tot域（插入線段左端點的總個數）會造成不同的影響，具體來說，在New操作中，tot值不會被同時加上（需要另外一個操作加上），然而在Free操作中，tot值會被同時清空，這樣就會導致在對某個結點清空（該結點包含在某個Free操作要清空的線段中）并打上0標記之后，如果緊接著又插入一條包含這個結點區間的新線段，則這個結點的0標記就會喪失，這樣在緊接著下傳的時候，其子結點的tot值就不會被清空（事實上已經被清空了）。所以，將tot域徹底轉移到另一棵線段樹里。
struct node {
int len, mr, lsc, rsc, sc;
} T[MAXN << 2];
struct node0 {
int tot;
bool mr;
} T0[MAXN << 2];
其中lsc、rsc、sc就是連續空閑段的長度（用左右歸中的方法維護），mr是一個整體賦值標記，在T中，mr的值若為-1表示無標記（未被整體賦值），若為0表示被整體清空，若大于0表示整體被一條線段覆蓋，mr值就是這條線段的編號（為區分不同線段，這里按照輸入順序對每一條New操作插入的線段以1、2……編號），在T0中，mr=1表示在Reset中被整體清空，mr=0表示無標記。
<2>操作處理：
1)Reset操作：將T、T0的根結點打上清空標記即可；
2)New：涉及到兩個操作，分別是找最左的長度為x的連續空閑段，以及插入一條線段。對于前者，可以根據lsc、rsc、sc的值，按照“先左子結點，再跨越兩個子結點，最后右子結點”的順序求得（詳見代碼）；對于后者就不用說了，太容易實現了（注意標記的處理以及upd，另外要插入一個tot）；
3)Free：也涉及兩個操作，分別是找一個點x所在的線段（插入過的線段）長度以及刪除一條線段，對于前者可將New插入過的所有線段的左右端點預存起來，然后找到代表區間[x, x]的結點的mr值（也就是結點x被編號為神馬的線段覆蓋），再在預存的線段中找到即可。對于后者，直接清空即可（不要在T0中打標記，而要單獨刪除一個tot）；
4)Get：直接利用T0中的tot找到第K小的值即可；
代碼