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/（。裸题。。测模板用。
