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/（。裸题。。测模板用。
Alca
Amber
Belleve Invis
Chensiting123
Edward_mj
Fotile96
Hlworld
Kuangbin
Liyaos
Lwins
LYPenny
Mato 完整版
Mikeni2006
Mzry
Nagatsuki
Neko13
Oneplus
Rukata
Seter
Sevenkplus
Sevenzero
Shirleycrow
Vfleaking
wangzhpp
Watashi
WJMZBMR
Wywcgs
XadillaX
Yangzhe
三途川玉子
About.me
Vijos
用线段树写的主席树被卡内存了。
求带标记的主席树应该怎么写阿…………
。。yy 了一个标程。感觉还可以。 /$:^ ^ 。