Mato is No.1

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

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