Mato is No.1

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

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