(1)Robotic Sort(HDU1890ZJU2985
本题主要考察的是对此类问题,序列中给定值的索引问题。
当Splay Tree用来处理一个序列的时候,其关键字就是序列中元素的下标,而不是元素的值。这样,如果要查找序列中给定的值的位置(假设序列中任意两个元素的值不相等)看起来就无法实现。其实也是有办法实现的:因为元素在树中的下标是永远不变的!也就是,设这个序列为A,如果A[i]在插入Splay Tree时的下标为j,那么在A[i]被删除之前,其下标一直是j,永远不会变(注意元素在序列中的下标和在树中的下标是不同的)。利用这一性质可以解决给定值的索引问题。
对于本题,每次将从序列中第i小的元素到序列中第i个元素(这里假定元素下标是从1开始的,而不是从0开始)之间的所有元素反转,并输出第i小的元素在反转之前的在序列中的下标。设B[i]为第i小的数的初始位置,S[i]为初始位置在第i位的元素的下标,B[i]和S[i]都可以通过预处理得到。然后,每次交换前,求出S[B[i]]在树中的排名(基本操作),再减1(因为有边界结点)就是该元素目前的位置,而序列中第i个元素就是树中第(i+1)小的元素,再执行交换即可。
不过需要千万注意的是本题的标记问题,在求S[B[i]]在树中的排名时,有可能其祖先结点上有标记,需要先遍历其所有的祖先结点,再逆向下放标记(标记只能自顶向下传)。另外在交换的时候需要求出S[B[i]]的后继,在求后继的过程中需要查找,此时千万别忘了下放标记(总的说,凡是有查找的地方,就有dm)
代码(本沙茶太弱了,是抄别人的,因此其算法和上面总结的可能有差别,神犇不要鄙视)

(2)SuperMemo(PKU3580
本题的6个操作中,add、reverse、insert、delete、min都不难搞,而revolve操作需要涉及到区间交换。
可以发现,所谓的旋转其实就是交换两个相邻区间,这对于功能极强的Splay Tree来说根本不难搞。
设这两个相邻区间为[x, y]与[y+1, z],假设它们均非空(也就是x<=y<z,因为若其中至少有一个区间是空区间,则交换没有意义),先找到树中x的前趋P与z的后继S(这里x、z等指的都是对应的结点,下同),将P伸展到根、将S伸展到根的右子结点处,则S的左子树就表示区间[x, z]。然后,设S的左子树的根结点(也就是S的左子结点)为N,在这棵子树中找到第1小的结点P0与第(y-x+2)小的结点S0(这需要涉及到找子树内第K小的操作,只要把找整棵树第K小的操作的root改为N即可),它们分别表示x与(y+1),这样将P0伸展到N处,将S0伸展到N的右子结点处,显然P0无左子树,S0的左子树T1表示区间[x+1, y],S0的右子树T2表示区间[y+2, z]。然后,先将S0从P0的右子结点移动到P0的左子结点,再将T1作为P0的右子树(注意移动是两步:插入和删除)。这样整棵子树的中序遍历结果变成了S0->T2->P0->T1,也就是[y+1, z]∪[x, y]。
另外本题的标记有点难搞,只需注意rev是逆向标记,以及查找与dm共存就行了。
代码
(3)Play with Chain(HDU3487)
这个米有神马好说的,里面的操作在SuperMemo里都有;
代码
(4)AHOI2006 文本编辑器(editor)
这题在这一类题里面算水的。对于光标,只要用一个值来维护就行了。
另外注意本题极为猥琐的2点(题目中米有说明):一是最初的文本并不是空的,而是有一个空格;二是执行GET操作时光标可能位于文本末尾,此时应输出空格;
代码
(5)HFTSC2011 高精度计算器(apc),题目见这个帖子
这题反映出了一个很囧的问题:有些信息会被rev整体破坏。
本题中的操作都是常见操作,但是本题所需要维护的信息却不是那么容易维护。本题要求维护一棵子树中所有结点所表示的元素序列(中序遍历结果)模一个指定的M的值。设F[i]为R^i mod M的值(这里R是进制,也就是题目中的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;
这个式子其实是很好理解的。
关键是,本题的猥琐之处并不在此。注意本题的rev操作,它会整体改变树中所有结点所记录的mod值,这时,如果再用上面这个式子来维护T[x].mod,就会出错,因为此时引用到的T[T[x].c[0]].mod和T[T[x].c[1]].mod都是过时的。解决这一问题只有一种方法:记录“逆mod”(rmod),意思是将整个元素序列反转后的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;
这样,在反转某序列的时候,直接将根结点的mod值和rmod值交换就行了。
像mod这样会被反转操作整体破坏的信息还有很多,比如NOI2005 sequence里面的lmax和rmax。如果真的遇到这类信息,只有采用上面的方法。
另外,本题第6、9、10个点有误。
代码

现在Splay Tree差不多弄完了,接下来还有N多知名的、不知名的高级数据结构……时间MS有些不够用了囧……

Feedback

# re: Splay Tree处理区间问题的几道好题及总结[未登录]  回复  更多评论   

2011-06-26 20:36 by xiaodao
楼主用Splay可以去修 link-cut Tree 撒。。

# re: Splay Tree处理区间问题的几道好题及总结  回复  更多评论   

2012-03-08 02:46 by boboaaa12345
LZ的(4)AHOI2006 文本编辑器(editor)
貌似WA了啊。。。求解释。。。

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理