Mato is No.1

平衡樹(shù)操作，尤其是Splay Tree的區(qū)間操作（當(dāng)線段樹(shù)用的那種），代碼長(zhǎng)且極易搞疵，當(dāng)操作多的時(shí)候，甚至可能調(diào)試的時(shí)間比寫代碼的時(shí)間都長(zhǎng)！
這里來(lái)總結(jié)一下平衡樹(shù)在實(shí)際應(yīng)用（編程）中的易疵點(diǎn)和調(diào)試技巧。
【平衡樹(shù)（這里主要指Splay Tree）的操作】
這個(gè)MS前面已經(jīng)總結(jié)過(guò)了，主要分以下幾類：
（1）基本操作：查找、單結(jié)點(diǎn)插入、單結(jié)點(diǎn)刪除、找第K小、求結(jié)點(diǎn)的排名、找指定結(jié)點(diǎn)的前趨和后繼；
（2）進(jìn)階操作：找給定的值在樹(shù)中的前趨和后繼、對(duì)一個(gè)序列建平衡樹(shù)、插入整棵子樹(shù)、刪除整棵子樹(shù)；
（3）區(qū)間操作（與線段樹(shù)的結(jié)合）：標(biāo)記（自頂向下）；
（4）區(qū)間操作（與線段樹(shù)的結(jié)合）：最大值、總和等自底向上維護(hù)的信息；
（5）一些特別猥瑣的操作（比如PKU3580的revolve）；
【主要函數(shù)及其易疵點(diǎn)】
（1）void sc(int _p, int _c, bool _d);
將_p的_d子結(jié)點(diǎn)（0左1右）置為_(kāi)c，這個(gè)就三句話，應(yīng)該不會(huì)搞疵；
（2）void upd(int x);
更新x記錄的一些信息（自底向上維護(hù)的信息，包括大小域sz），這個(gè)，有幾個(gè)信息就寫幾句話就行了，不易搞疵；
（3）void rot(int x);
旋轉(zhuǎn)操作，將x旋轉(zhuǎn)到其父結(jié)點(diǎn)的位置。這個(gè)函數(shù)中有兩個(gè)易疵點(diǎn)：一是若x的父結(jié)點(diǎn)為根，則需要在旋轉(zhuǎn)后將根置為x，且將x的父結(jié)點(diǎn)置為0（特別注意這個(gè)）；二是若x的父結(jié)點(diǎn)不為根，則需要將x的父結(jié)點(diǎn)的父結(jié)點(diǎn)的對(duì)應(yīng)子結(jié)點(diǎn)（原來(lái)是x的父結(jié)點(diǎn)的那個(gè)）置為x；另外旋轉(zhuǎn)完成后別忘了更新；
（4）void splay(int x, int r);
伸展操作，將x伸展到r的子結(jié)點(diǎn)處，這個(gè)操作是最核心的操作，只要記住了過(guò)程，且rot不搞疵，這個(gè)也就不會(huì)搞疵；
（5）void dm(int x);
對(duì)于有標(biāo)記的結(jié)點(diǎn)的下放標(biāo)記操作，極易疵！
首先，對(duì)于任何結(jié)點(diǎn)，標(biāo)記一打上就必須立即生效，因此除了將x的標(biāo)記取消、x的兩個(gè)子結(jié)點(diǎn)（如果存在的話）打上標(biāo)記外，還要更新兩個(gè)子結(jié)點(diǎn)的一些域（當(dāng)然這里更新千萬(wàn)不能用upd更新）；
其次，要搞清楚x的每一個(gè)標(biāo)記的類型，是疊加型標(biāo)記（如整體加上某一個(gè)數(shù)的標(biāo)記）、覆蓋型標(biāo)記（如整體置為某一個(gè)數(shù)的標(biāo)記）還是逆向標(biāo)記（如是否翻轉(zhuǎn)過(guò)的標(biāo)記，因?yàn)榉D(zhuǎn)兩次等于沒(méi)轉(zhuǎn)），然后在下放標(biāo)記的時(shí)候注意寫法（因?yàn)閤的子結(jié)點(diǎn)原來(lái)可能也有標(biāo)記，此時(shí)只有覆蓋型標(biāo)記需要將x的子結(jié)點(diǎn)的原來(lái)的標(biāo)記覆蓋掉，對(duì)于疊加型標(biāo)記，應(yīng)為加法運(yùn)算，對(duì)于逆向標(biāo)記，應(yīng)為取反操作，還有其它類型的標(biāo)記分別處理）；
最后還有一點(diǎn)，就是x的左子結(jié)點(diǎn)或右子結(jié)點(diǎn)可能不存在（0），此時(shí)就不能對(duì)這里的0號(hào)結(jié)點(diǎn)下放標(biāo)記。
（6）int Find_Kth(int x, int K);
在以結(jié)點(diǎn)x為根的子樹(shù)中找第K小的結(jié)點(diǎn)，返回結(jié)點(diǎn)編號(hào)；若省略x，默認(rèn)x=root（即在整棵樹(shù)中找）；
這個(gè)一般不會(huì)搞疵，注意兩個(gè)地方即可：一是有mul域的時(shí)候需要考慮mul域，二是結(jié)點(diǎn)如果有標(biāo)記，需要在找的時(shí)候下放標(biāo)記。（凡是查找操作，包括插入新結(jié)點(diǎn)時(shí)的查找，在查找過(guò)程中必須不斷下放標(biāo)記，因?yàn)椴檎抑蠛芸赡芫鸵煺梗?br />（7）void ins(int _v);
       void ins(int x, int _v)
插入一個(gè)值為_(kāi)v的結(jié)點(diǎn)。前者是普通插入，后者是用Splay Tree處理序列（當(dāng)線段樹(shù)用）時(shí)的插入，表示在第x小的結(jié)點(diǎn)后插入；
前者注意有三種情況：樹(shù)為空；樹(shù)非空且值為_(kāi)v的結(jié)點(diǎn)不存在；樹(shù)非空且值為_(kāi)v的結(jié)點(diǎn)已存在；
后者需要注意，在將第x小的結(jié)點(diǎn)伸展到根，將第(x+1)小的結(jié)點(diǎn)伸展到根的右子結(jié)點(diǎn)，再插入后，需要upd上述兩個(gè)結(jié)點(diǎn)（注意upd順序）；
（8）void del(int x);
將結(jié)點(diǎn)x刪除。這個(gè)一般不會(huì)搞疵，唯一要注意的一點(diǎn)是刪除后的upd；
（9）打標(biāo)記操作（add、reverse、makesame等）：
其實(shí)打標(biāo)記操作的代碼量是很少的，關(guān)鍵就是對(duì)于不同標(biāo)記要分別處理，同（5）；
（10）各種詢問(wèn)操作：
這個(gè)直接調(diào)出相應(yīng)的域即可，幾乎不可能搞疵；
（11）極其猥瑣的操作（revolve等）：
這個(gè)屬于最易疵的操作（否則就體現(xiàn)不出其猥瑣了）：
首先要搞清楚這個(gè)操作的具體過(guò)程，不要連具體過(guò)程都搞疵了，這樣寫出來(lái)的代碼肯定是疵的；
然后，注意一些非常猥瑣的細(xì)節(jié)問(wèn)題（很多時(shí)候，本沙茶都是栽在細(xì)節(jié)上的）；
另外，這些操作中一般都會(huì)出現(xiàn)多次伸展，別忘了伸展后的upd；
（12）其它易疵點(diǎn)：
[1]“移動(dòng)”是由“插入”和“刪除”兩部分組成的，因此凡是涉及到“移動(dòng)”類的操作（如將某棵子樹(shù)或某個(gè)結(jié)點(diǎn)移動(dòng)到另一個(gè)位置等），必須要同時(shí)出現(xiàn)“插入”和“刪除”，而不能只插入不刪除；
[2]注意檢查主函數(shù)main()中是否有搞疵的地方；

易疵點(diǎn)也就這么多了，下面是調(diào)試技巧：
【Splay Tree調(diào)試技巧】
（1）先用樣例調(diào)試，保證樣例能夠通過(guò)（注意，樣例中必須包含所有題目中給出的操作，如果不是這樣，那在調(diào)試完樣例后還要加一組包含所有題目中給出的操作的小數(shù)據(jù)）；
（2）然后用mkdt造大數(shù)據(jù)，一般平衡樹(shù)操作題的合法數(shù)據(jù)都不難造，只要注意別越界就行了；
（3）在調(diào)試過(guò)程中應(yīng)不斷少量增大數(shù)據(jù)規(guī)模，因?yàn)樵谀苷页鰡?wèn)題的情況下，數(shù)據(jù)規(guī)模越小越好；
（4）如果調(diào)試過(guò)程中發(fā)現(xiàn)死循環(huán)或者RE：
[1]首先輸出每個(gè)操作，找出是在哪個(gè)操作處出了問(wèn)題；
[2]進(jìn)入該操作內(nèi)部檢查，也就是把該操作的代碼讀一遍，一般都能找出問(wèn)題；
[3]如果找不出問(wèn)題，可以進(jìn)入該操作內(nèi)部跟蹤檢查；
[4]如果跟蹤檢查仍然沒(méi)找出問(wèn)題，那可能是該操作是對(duì)的，而其它操作出了問(wèn)題，此時(shí)可以弄一個(gè)vst，把整棵樹(shù)遍歷一下，找出真正出問(wèn)題的操作，轉(zhuǎn)[2]；
（5）排除了死循環(huán)或RE后，接下來(lái)就是檢查輸出結(jié)果是否正確了：
[1]對(duì)于小規(guī)模數(shù)據(jù)可人工計(jì)算檢查，對(duì)于較大規(guī)模數(shù)據(jù)則必須采用對(duì)照方法，即弄一個(gè)模擬法的代碼，保證該代碼正確，然后進(jìn)行對(duì)照；
[2]如果發(fā)現(xiàn)加入遍歷時(shí)，結(jié)果正確，但去掉遍歷后結(jié)果不正確，則表明是處理結(jié)點(diǎn)標(biāo)記的時(shí)候出了問(wèn)題（因?yàn)樵诒闅v過(guò)程中需要下放標(biāo)記），進(jìn)入dm或加標(biāo)記操作中檢查即可；
[3]其它情況下，可以在遍歷中輸出整個(gè)序列（或整棵樹(shù)），進(jìn)行對(duì)照，找出問(wèn)題所在；
[4]如果數(shù)據(jù)過(guò)大，操作過(guò)多，人工分析時(shí)間較長(zhǎng)，就只能采用讀代碼的方式檢查了；
（6）最后，用mkdt造一個(gè)最大規(guī)模的數(shù)據(jù)，檢查是否TLE、是否越界（數(shù)組是否開(kāi)小）；
如果以上各點(diǎn)全部通過(guò)，就可以宣布AC了。