（1）Robotic Sort（
HDU1890、
ZJU2985）
本題主要考察的是對此類問題，序列中給定值的索引問題。
當(dāng)Splay Tree用來處理一個(gè)序列的時(shí)候，其關(guān)鍵字就是序列中元素的下標(biāo)，而不是元素的值。這樣，如果要查找序列中給定的值的位置（假設(shè)序列中任意兩個(gè)元素的值不相等）看起來就無法實(shí)現(xiàn)。其實(shí)也是有辦法實(shí)現(xiàn)的：因?yàn)樵卦跇渲械?span style="color: red">
下標(biāo)是永遠(yuǎn)不變的！也就是，設(shè)這個(gè)序列為A，如果A[i]在插入Splay Tree時(shí)的下標(biāo)為j，那么在A[i]被刪除之前，其下標(biāo)一直是j，永遠(yuǎn)不會變（注意元素在序列中的下標(biāo)和在樹中的下標(biāo)是不同的）。利用這一性質(zhì)可以解決給定值的索引問題。
對于本題，每次將從序列中第i小的元素到序列中第i個(gè)元素（這里假定元素下標(biāo)是從1開始的，而不是從0開始）之間的所有元素反轉(zhuǎn)，并輸出第i小的元素在反轉(zhuǎn)之前的在序列中的下標(biāo)。設(shè)B[i]為第i小的數(shù)的
初始位置，S[i]為
初始位置在第i位的元素的下標(biāo)，B[i]和S[i]都可以通過預(yù)處理得到。然后，每次交換前，求出S[B[i]]在樹中的排名（基本操作），再減1（因?yàn)橛羞吔缃Y(jié)點(diǎn)）就是該元素目前的位置，而序列中第i個(gè)元素就是樹中第(i+1)小的元素，再執(zhí)行交換即可。
不過需要千萬注意的是本題的標(biāo)記問題，在求S[B[i]]在樹中的排名時(shí)，有可能其祖先結(jié)點(diǎn)上有標(biāo)記，需要先遍歷其所有的祖先結(jié)點(diǎn)，再逆向下放標(biāo)記（標(biāo)記只能自頂向下傳）。另外在交換的時(shí)候需要求出S[B[i]]的后繼，在求后繼的過程中需要查找，此時(shí)千萬別忘了下放標(biāo)記（總的說，凡是有查找的地方，就有dm）
代碼（本沙茶太弱了，是抄別人的，因此其算法和上面總結(jié)的可能有差別，神犇不要鄙視）
（2）SuperMemo（
PKU3580）
本題的6個(gè)操作中，add、reverse、insert、delete、min都不難搞，而revolve操作需要涉及到區(qū)間交換。
可以發(fā)現(xiàn)，所謂的旋轉(zhuǎn)其實(shí)就是交換兩個(gè)相鄰區(qū)間，這對于功能極強(qiáng)的Splay Tree來說根本不難搞。
設(shè)這兩個(gè)相鄰區(qū)間為[x, y]與[y+1, z]，假設(shè)它們均非空（也就是x<=y<z，因?yàn)槿羝渲兄辽儆幸粋€(gè)區(qū)間是空區(qū)間，則交換沒有意義），先找到樹中x的前趨P與z的后繼S（這里x、z等指的都是對應(yīng)的結(jié)點(diǎn)，下同），將P伸展到根、將S伸展到根的右子結(jié)點(diǎn)處，則S的左子樹就表示區(qū)間[x, z]。然后，設(shè)S的左子樹的根結(jié)點(diǎn)（也就是S的左子結(jié)點(diǎn)）為N，在這棵子樹中找到第1小的結(jié)點(diǎn)P0與第(y-x+2)小的結(jié)點(diǎn)S0（這需要涉及到找子樹內(nèi)第K小的操作，只要把找整棵樹第K小的操作的root改為N即可），它們分別表示x與(y+1)，這樣將P0伸展到N處，將S0伸展到N的右子結(jié)點(diǎn)處，顯然P0無左子樹，S0的左子樹T1表示區(qū)間[x+1, y]，S0的右子樹T2表示區(qū)間[y+2, z]。然后，先將S0從P0的右子結(jié)點(diǎn)移動(dòng)到P0的左子結(jié)點(diǎn)，再將T1作為P0的右子樹（注意移動(dòng)是兩步：插入和刪除）。這樣整棵子樹的中序遍歷結(jié)果變成了S0->T2->P0->T1，也就是[y+1, z]∪[x, y]。
另外本題的標(biāo)記有點(diǎn)難搞，只需注意rev是逆向標(biāo)記，以及查找與dm共存就行了。
代碼（3）Play with Chain(
HDU3487)
這個(gè)米有神馬好說的，里面的操作在SuperMemo里都有；
代碼（4）
AHOI2006 文本編輯器(editor)這題在這一類題里面算水的。對于光標(biāo)，只要用一個(gè)值來維護(hù)就行了。
另外注意本題極為猥瑣的2點(diǎn)（題目中米有說明）：一是最初的文本并不是空的，而是有一個(gè)空格；二是執(zhí)行GET操作時(shí)光標(biāo)可能位于文本末尾，此時(shí)應(yīng)輸出空格；
代碼（5）HFTSC2011 高精度計(jì)算器(apc)，題目見
這個(gè)帖子；
這題反映出了一個(gè)很囧的問題：有些信息會被rev整體破壞。
本題中的操作都是常見操作，但是本題所需要維護(hù)的信息卻不是那么容易維護(hù)。本題要求維護(hù)一棵子樹中所有結(jié)點(diǎn)所表示的元素序列（中序遍歷結(jié)果）模一個(gè)指定的M的值。設(shè)F[i]為R^i mod M的值（這里R是進(jìn)制，也就是題目中的K），則有：
T[x].mod = (T[T[x].c[0]].mod * F[T[T[x].c[1]].sz + 1] + T[x].v * F[T[T[x].c[1]].sz] + T[T[x].c[1]].mod) % M;
這個(gè)式子其實(shí)是很好理解的。
關(guān)鍵是，本題的猥瑣之處并不在此。注意本題的rev操作，它會整體改變樹中所有結(jié)點(diǎn)所記錄的mod值，這時(shí)，如果再用上面這個(gè)式子來維護(hù)T[x].mod，就會出錯(cuò)，因?yàn)榇藭r(shí)引用到的T[T[x].c[0]].mod和T[T[x].c[1]].mod都是過時(shí)的。解決這一問題只有一種方法：記錄“逆mod”(rmod)，意思是將整個(gè)元素序列反轉(zhuǎn)后的mod，即：
T[x].rmod = (T[T[x].c[1]].rmod * F[T[T[x].c[0]].sz + 1] + T[x].v * F[T[T[x].c[0]].sz] + T[T[x].c[0]].rmod) % M;
這樣，在反轉(zhuǎn)某序列的時(shí)候，直接將根結(jié)點(diǎn)的mod值和rmod值交換就行了。
像mod這樣會被反轉(zhuǎn)操作整體破壞的信息還有很多，比如NOI2005 sequence里面的lmax和rmax。如果真的遇到這類信息，只有采用上面的方法。
另外，本題第6、9、10個(gè)點(diǎn)有誤。
代碼現(xiàn)在Splay Tree差不多弄完了，接下來還有N多知名的、不知名的高級數(shù)據(jù)結(jié)構(gòu)……時(shí)間MS有些不夠用了囧……