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