某岛

… : "…アッカリ~ン . .. . " .. .
August 7, 2012

SPOJ 11470. To the moon

Brief description:

动态维护序列,要求支持区间增减,历史区间询问,以及回档到某个历史状态。。
(。。回档后不可返回。。。

Tucao:

。。嘛。。题目出成这样我也没什么好辩解的了。。
原本的题目还有一个 retroact 操作。。允许对一个历史的询问做修改。。然后回到现实看看发生了哪些变化。。
而且强制在线。。这样的话是。。部分可持久化条件下的一阶追朔性数据结构。。
一般情况下好像没法做。。但是在操作同时具有满足逆操作存在、和交换律的情况下。。可以用主席树维护。。。

。。不过后来发现这个东西等价于一个二维的线段树问题。。。觉得没什么意思。。就去掉了。。。
。。。于是就变得比较保守。。而且想到去年的题目还防了 AK 。。所以这次本来也是。。想出一道普通程度的题。。
(。。最近在读 《okasaki》。。发现发现去年那只题目的方法居然有名字的。。(。。。 Global Reconstruction。。。

。。(。。然后之前以为是下个星期二多校。。所以午睡的时候被叫醒了。。。上来看了一下发现 hud 的题目描述居然粘错了。。
。明明在 Hoj 和 Spoj 都是排版好了的啊。。而且居然是 HIT 专场。。。本来像是 1011 这种题。。就不可能应该让它出现在多校之中!。。我也只是验了自己的题目。。中间衔接的过程也做的很不好。。非常抱歉!。。。。。

Analysis:

本题考查可持久化数据结构,可持久化数据结构可以依据需求,可分为。。

1. Partially persistent (部分持久化)
允许对历史查询,但是只能对当前版本进行修改。
用图论术语描述即是线性结构。。

2. Fully persistent (完全持久化)
在部分持久化的基础上,支持在历史版本上修改。
即是树形结构。。。

3. Confluently persistent (汇聚持久化)
在完全持久化的基础上,允许用两个(或多个)历史版本形成一个新结点。。
图论描述即为 DAG 。。。
http://en.wikipedia.org/wiki/Persistent_data_structure

。。(SGI STL 中的 Rope (重绳)就是第三种形态的一个例子。。
。。(另外根据 Erik Demaine 的说法还存在着更一般的 Functional persistent (函数式持久化)…
http://fanhq666.blog.163.com/blog/static/81943426201161095456671/
http://ocw.mit.edu/courses/electrical-engineering-and-computer-science/6-851-advanced-data-structures-spring-2010/lecture-notes/

。。本题是介于第 1 类和第 2 类之间的形态。。部分持久化,
。。然后允许回档到某个历史状态。。(但不要求直接从历史状态处修改。。。

在线做法:

1. 带标记的主席树(。以 “Path Copying” 方式实现的线段树。。

。O(logN) 询问、O(1) 回档。。另外主席树本身是 Fully persistent 的。。。
。。但是空间复杂度 O(mlogn) 且常数较高。。比较吃内存。。

(。具体参见陈丽洁的课件。。
http://hi.baidu.com/wjbzbmr/blog/item/a7f4a5996c328b95c9eaf489.html

2. “主席数组”(以 “Fat Node” 方式实现的树状数组。。。

。。树状数组的每个结点维护一个记录时间戳的栈,
询问时遍历到每个结点再二分查找。。 O(nlog^2n) 询问。。。。
空间复杂度 O(mlogn)。。

(对于回档操作。。我们使用暴力弹栈。。
每个结点至多被弹出一次,总共 O(nlogn) 个结点。。。

离线做法:

。。堆维护询问(或者直接插到相应时刻的链表里。。)。。。 栈维护操作。。每次遇到回档操作,则弹出所有至此时刻的询问。。
。最后再弹到 0 时刻即可。。每个操作入栈出栈各一次。。
。。询问复杂度 O(nlogn)。。空间复杂度 O(nlogn)。。

带标记的主席树。。(12s+-。。。110 M 内存。。
主席数组(17s+-。。。
离线算法(5s+-。。。

(预计 AC 队伍会有 9~19 支?。。而且比赛的话大概都是会写这种离线算法的吧 ~。。。

External link:

http://www.spoj.pl/problems/TTM/
http://www.shuizilong.com/house/archives/poj-3468-a-simple-problem-with-integers/(。裸题。。测模板用。