某島

… : "…アッカリ~ン . .. . " .. .
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/
https://www.shuizilong.com/house/archives/poj-3468-a-simple-problem-with-integers/(。裸題。。測模板用。