Posted on 2012-11-25 14:54
Mato_No1 阅读(626)
评论(0) 编辑 收藏 引用 所属分类:
线段树 、
平衡树 、
专题:数据结构动态模拟问题
原题地址本沙茶去年曾经用双线段树的方法捉了这题（详见
这里），最近重新审视这题发现，借助平衡树，可以得到更简单的方法。
题目大意：
有一个长度为N的内存条，每个位置的状态有占用和不占用两种，有4种操作：
（1）Reset：清空所有内存（即将所有位置的状态改为不占用，删除所有内存块）；
（2）New x：申请一个新的内存块，即找到一个长度为x的连续不占用位置区间，将它们标记为占用，若有多个这样的区间，取最左边的，若木有输出Reject New；
（3）Free x：在已申请的内存块中，找到包含位置x的并释放（将该内存块删除，同时其占用的所有位置改为不占用），若木有内存块包含位置x，则输出Reject Free；
（4）Get x：找出已申请的内存块中，左起第x个，并输出其左端点；若已申请的内存块数目不足x个，则输出Reject Get。
可以发现，每个已经申请的内存块尽管代表一段区间，但仍然是独立的单位，因此，可以把内存块当成结点，用平衡树维护（关键字为内存块的左端点位置），New操作中内存块的插入与Free操作中内存块的删除均在此平衡树内进行，Reset操作只需要将整棵树销毁即可。
问题是，在New操作中，需要找到一个长度为x的连续不占用区间，而连续的不占用区间并不是独立的单位，因此需要使用线段树维护。在线段树中，需要维护<1>结点区间内最长连续不占用块的长度；<2>结点区间左端、右端连续不占用块的长度（否则无法维护<1>）；同时，由于在New操作中需要区间整体改占用，Free操作中又需要区间整体改不占用，所以应当支持整体改值的标记，对于Reset操作，只需要全部位置改不占用即可（不能重新建树！！）；
这样，利用一棵平衡树加一棵线段树，就可以得到一个很简单的方法了（代码量是双平衡树或双线段树的一半左右）；
这题的启示是，在解决数据结构统计类题的时候，到底选用什么样的数据结构，是有讲究的，因为它将直接影响到编程复杂度。一般来说，线段树比平衡树好写，但是对本题而言，双线段树反而不如平衡树加线段树好写，这是因为对于内存块使用平衡树维护比使用线段树维护更好。在以后做这种题的时候，要多想一下，找到简便方法。