郭华阳《RMQ与LCA问题》.ppt

RMQLCA问题 湖南省长郡中学 郭华阳 全文总揽 问题的提出 问题的解决 问题的应用 I. 问题的提出 问题的提出 LCA：基于有根树最近公共祖先问题 LCA（T，u，v）：在有根树T中，询问一个距离根最远的结点x，使得x同时为结点u、v的祖先 问题的提出 RMQ：区间最小值询问问题 RMQ（A，i，j）：对于线性序列A中，询问区间[i，j]上的最小值 特别的，若线性序列A任意两相邻元素相差为±1，那么建立在A上的RMQ称为±1RMQ RMQLCA在信息学竞赛中 各种竞赛试题中，如上海2003年省选的登山、 2002年POI的商务旅行等，都是这类问题的应用及扩展 熟练的掌握及解决RMQLCA问题，对于研究和竞赛都是十分重要的 II. 问题的解决 RMQLCA问题的解决 在研究人员的努力下，RMQLCA问题已经获得了比较完善的解决方案，这里我们只列出一些常用算法的适用范围以及他们的时空复杂度： RMQLCA问题的解决 我们以O(f(N)) – O(g(N))描述一个在线算法，在O(f(N))的时间内完成预处理，在O(g(N))的时间内完成一次询问 以O(f(N) + g(N)×Q)描述一个离线算法的时间消耗 RMQLCA问题的解决 这些算法各自具有特点，但是针对问题过于狭窄。下文中我们将会看到，RMQ与LCA问题是可以互相转化的，这就大大扩宽了以下算法的应用面 RMQ向LCA的转化 考察一个长度为N的序列A，按照如下方法将其递归建立为一棵树： 设序列中最小值为Ak，建立优先级为Ak的根节点Tk； 将A(1…k–1)递归建树作为Tk的左子树； 将A(k+1…N)递归建树作为Tk的右子树； 不难发现，这棵树是一棵优先级树 A = (7 5 8 1 10) A = (7 5 8 1 10) A = (7 5 8 1 10) A = (7 5 8 1 10) A = (7 5 8 1 10) A = (7 5 8 1 10) A = (7 5 8 1 10) RMQ向LCA的转化 对于RMQ(A，i，j)： 设序列中最小值为Ak，若k∈[i, j]，那么答案为k； 若k j，那么答案为RMQ(A1..k-1，i，j)； 若k i，那么答案为RMQ(AK+1..N，i，j)； 不难发现RMQ(A，i，j) = LCA(T，i，j)！ 这就证明了RMQ问题可以转化为LCA问题 LCA向RMQ的转化 对有根树T进行DFS，将遍历到的结点按照顺序记下，我们将得到一个长度为2N – 1的序列，称之为T的欧拉序列F 每个结点都在欧拉序列中出现，我们记录结点u在欧拉序列中第一次出现的位置为pos(u) LCA向RMQ的转化 根据DFS的性质，对于两结点u、v，从pos(u)遍历到pos(v)的过程中经过LCA(u, v)有且仅有一次，且深度是深度序列B[pos(u)…pos(v)]中最小的 即LCA(T, u, v) = RMQ(B, pos(u), pos(v))，并且问题规模仍然是O(N)的 LCA向RMQ的转化 根据DFS的性质，对于两结点u、v，从pos(u)遍历到pos(v)的过程中经过LCA(u, v)有且仅有一次，且深度是深度序列B[pos(u)…pos(v)]中最小的 这就证明了LCA问题可以转化成RMQ问题 LCA与RMQ问题可以互相转化，并且可以在O(N)的时间内完成！ RMQLCA算法关系图 III. 问题的应用 问题的应用 RMQLCA问题在算法研究及信息学竞赛中都发挥着十分重要的作用，它主要是以一种经典算法及解题思想的形式出现 本文主要以讨论一道例题： 水管局长（2006年冬令营试题） 水管局长（原题） SC省MY市有着庞大的地下水管网络，嘟嘟是MY市的水管局长（就是管水管的啦），嘟嘟作为水管局长的工作就是：每天供水公司可能要将一定量的水从x处送往y处，嘟嘟需要为供水公司找到一条从A至B的水管的路径，接着通过信息化的控制中心通知路径上的水管进入准备送水状态，等到路径上每一条水管都准备好了，供水公司就可以开始送水了。嘟嘟一次只能处理一项送水任务，等到当前的送水任务完成了，才能处理下一项。 在 处理每项送水任务之前，路径上的水管都要进行一系列的准备操作，如清洗、消毒等等。嘟嘟在控制中心一声令下，这些水管的准备操作同时开始，但由于各条管道 的长度、内径不同，进行准备操作需要的时间可能不同。供水公司总是希望嘟嘟能找到这样一条送水路径，路径上的所有