Mato is No.1

額……最近兩天光顧著刷題忘了總結了……正好現在把總結的東東全部補上吧囧……

【重復次數mul】
在前面第一篇總結Splay Tree的時候就提到了結點的重復次數(mul)域，這個東東至今在網上還米看見有犇用（在本沙茶見過的范圍內），但是不可否認的是這個域在某些情況下幾乎是“必須使用”的。
所謂重復次數，就是將樹中所有值(v)相同的結點全部合并成一個，這些結點的總個數就是合并后的結點的mul值。比如，在一棵空樹中插入3個值為5的結點后，在使用mul域的情況下，樹中只有一個結點，其v值為5，mul值為3。
在平衡樹中，值相同的結點確實非常礙事。按照二叉查找樹的定義：“要么是一棵空樹，要么是一棵滿足以下條件的非空樹：根結點左子樹中所有結點的值均小于根結點，根結點右子樹中所有結點的值均大于根結點，且根的左右子樹均為二叉查找樹”，在二叉查找樹中，是不應該出現值相同的結點的?？墒窃趯嶋H問題中，出現值相同的結點幾乎是不可避免的。此時，樹的定義就會變得非常模糊，也就是要把二叉查找樹定義中的“小于”全部改為“小于等于”，“大于”全部改為“大于等于”。這樣定義的樹在一般情況下也米有神馬問題，但是在找前趨(Pred)和找后繼(Succ)操作中，問題就來了。因為根結點的前趨和后繼的值可能與根結點相等（比如 HNOI2004 寵物收養所 那一題），這時，根結點的前趨既有可能在左子樹里，也有可能在右子樹里，根結點的后繼也一樣。此時，這兩個操作就無法進行了。
【mul域的維護】
mul域其實可以看成結點的一個本身屬性，和v一樣。因此在旋轉、伸展操作中任何結點的mul值都是不會改變的?？赡芨淖兘Y點mul值的地方只有兩處：一是插入，二是刪除。在插入一個值為_v的結點的時候，如果發現值為_v的結點在樹中已經存在，則只會將這個結點的mul值加1，而不是真正插入一個新的結點。同樣的，在刪除一個結點的時候，如果這個結點的mul值大于1，則只會將這個結點的mul值減1，而不是真正刪除。
【mul域的作用】
mul域最主要的作用就是解決值相同的結點對于某些操作的影響。另外，mul域的引入可以減少樹中結點的總個數（尤其是當插入的結點數很多而結點的值的范圍不大的時候），從而降低時間復雜度（準確來說可以降低常數）。
【Splay Tree的進階操作】
<1>找非根結點的前趨和后繼。
Splay Tree由于有伸展操作，可以將要求前趨或后繼的點伸展到根再求前趨或后繼。如果要不通過伸展操作找一個非根結點的前趨或后繼怎么辦？
設這個結點為x。如果x有左子結點，則x的前趨就是x的左子結點的右鏈上的最后一個結點；如果x沒有左子結點，則x的前趨就是從x開始往上（往x的祖先）查找，直到找到第一個是其父結點的右子結點的結點為止，則這個結點的父結點就是x的前趨（或者說，就是不斷沿著x的父結點往上找，一開始都是往右的，找到第一個往左的就行了）。后繼則正好相反。證明可以用中序遍歷。
<2>找某個值v0的前趨和后繼（值為v0的結點在樹中不一定存在）。
所謂v0的前趨和后繼，就是指在樹中值小于（也有的是不大于）v0的最大的結點的值，和樹中值大于（也有的是不小于）v0的最小的結點的值。在有了操作（1）【不通過伸展操作找非根結點的前趨和后繼】以后，這個操作變得極為容易：先進行普通的查找操作（查找值為v0的結點），如果能找到，則剩下的步驟就和操作（1）一樣了；如果找不到，則必然是找到某個空結點（0）處，假設在這里插入一個值為v0的結點（只是假設，不是真插入），則該結點顯然是沒有左子結點的，因此就是“從該結點開始往上查找，直到找到第一個是其父結點的右子結點的結點為止，則這個結點的父結點就是該結點的前趨”，也就是v0的前趨；后繼類似。
在查找過程中可以進行一個常數優化：設點i為查找過程中“右轉”的最后一個結點（即找到該結點后，接下來是該結點的右子結點），每次往右子結點轉的時候就更新i，則最后結點i就是值v0的前趨；后繼類似。
<3>刪除所有值在某區間內的結點（這個區間可以是開區間、閉區間或半開半閉區間）。
以開區間為例：刪除樹中所有值在(l, r)范圍內的結點。先找到l的前趨P和r的后繼S（注意這里的前趨和后繼是包括“等于”的），然后將P伸展到根，S伸展到P的右子結點處，則S的左子樹中就是所有值在(l, r)范圍內的結點，直接刪掉這棵子樹即可（注意刪除后要更新S和P）；若改為閉區間，則將前趨和后繼中的“等于”去掉（即必須是小于或大于）；半開半閉區間則一半按開區間處理，一半按閉區間處理。問題是，如果點P或點S不存在怎么辦。有兩種解決辦法，一是若P和S之一存在，則將其伸展到根，然后直接刪掉其左子樹或右子樹即可；若P和S都不存在，則樹為空，直接將root置為0即可；二是按照sequence的辦法，加入兩個邊界結點，當前趨或后繼不存在時就認為是邊界結點。
其實不光是刪除，在找到了這棵子樹后可以對它進行一些整體操作，從而讓Splay Tree具有線段樹的功能（這個在下面的NOI2005 sequence那一題里面會總結）。
<4>插入一棵樹（當然這棵樹也是Splay Tree，并且原樹中的結點值序列與新樹中的結點值序列不相交）。
有時候，題目中會連續出現很多插入操作，中間沒有其它操作，此時，與其一個一個插入，還不如將它們先建成一棵樹（建樹的方法在下一篇里總結），再整體插入。整體插入的方法：設L和R分別是新樹里值最小的結點和值最大的結點，在原樹中找到L的前趨P和R的后繼S，將P伸展到根，S伸展到P的右子結點處，由于原樹中的結點值序列與新樹中的結點值序列不相交（也就是原樹中的結點值要么小于L的值，要么大于R的值），因此S無左子結點，此時將新樹作為S的左子樹即可。