Skip to content

实时离散化:NOI2003 editor另解

NOI2003的editor(文本编辑器)一题的标准解法是“块状链表”。这个东西我以前没有写过,怎么想都觉得无法将这个东西妥帖地实现。找到的一个这道题的C++程序竟然有三百多行,让我看得着实很恶心。这道题能不能不用这种很不优美的数据结构来解决呢?答案是肯定的!

我把我解决这个问题时使用的技术称为“实时离散化”。首先解释离散化,一种合适的理解就是将需要处理的序列中的某些连续的区间当作一个元素来操作,以减少总的元素数量。对于这道题而言,如果我们事先能够知道“在哪些字母的前后会插入一个区间”“在哪些字母的前后会有区间被删除”,把这些字母称为“关键字母”,用一个关键字母来代表它与它后面的所有非关键字母,就可以大大的降低时间复杂度了。因为INSERT和DELETE的操作总数不超过4000次,“关键字母”的总数也不会超过4000*2个,这样就相当于所有的插入删除操作都在最多8000个(而非2000000个)元素组成的串上进行,当然就会很快了。问题是,我们无法在一个字母被插入时判断出它是否会在将来成为“关键字母”,也就是说,无法像某些题目一样只做一次初始的离散化,我们的“离散化”必须是“实时”的,也就是,必须实时的维护可以被一同处理的区间。

听上去有点玄妙,其实很简单。用一个很长的字符数组保存曾经被插入的所有字符串,当前正在编辑的文本用一个区间的数组来表示,每个区间代表它在前述字符数组中的位置。当需要在某个区间的中间插入时,只需按照这个被插入的位置将这个区间分裂成两个,再在两个新形成的区间的中间插入就可以了。同样,删除时也只需要按照需要被删除的文本两端将它们所在的区间分裂成两个,然后删除连续的若干个区间就可以了。设修改操作一共做了M次,则任何时候的区间总数不会超过2M个,所以每次操作的时间复杂度都是O(M),所有修改操作的总时间复杂度是O(M^2),而且常数很小,由于M<=4000,是完全可以承受的。INSERT和DELETE都实现了,GET也很好实现,挨个输出就行了,PREV和NEXT更是常数时间而已,最多可达到50000次的MOVE呢?如果每个MOVE的复杂度也都是O(M)似乎会有超时的危险。注意到这样一个明显的事实:若有连续的MOVE操作,只需要做最后一次的操作即可。经过这样的处理,需要实际做的MOVE操作大约也只是O(M)的级别。

对于这类在序列上进行添加、删除、反序等修改的题目来说,设修改操作有M次,序列的最大长度为N,块状链表的复杂度是O(M*N^0.5),“实时离散化”的复杂度是O(M^2)或者O(M^2+N),可见它在很多情况下是很有代替块状链表的可能的。对于某些题目而言,我认为它是相对于块状链表的一个更高层的抽象,所以编程要简单优雅很多(我的堆砌着大堆短函数的拖沓程序用了156行,其中核心的部分仅有不到100行),也不失效率。对于本题来说,我的程序可以P4 2.oG的电脑上最大数据1.6s左右,是可以AC的。但是,“实时离散化”还是不能完全代替块状链表,比如说当M与N同阶的时候就会退化成O(N^2)(因为已经失去了离散化的意义了),而块状链表仍然保持着O(N^1.5)。

示例程序:
editor.cpp

Post a Comment

Your email is never published nor shared. Required fields are marked *
*
*