P1383 高级打字机——字典树与栈
初见思路
因为要撤回的是操作，所以先以操作为对象
结果发现嵌套问题过于麻烦
再试一次
但是要维护的事实上是这个序列，研究序列的变化情况
如果给每一次操作建立一整个序列版本的话，就可以直接不管那些嵌套结构了
发现每次都只在末尾加字符，所以每次操作的时候前方都有大量的重复部分
于是想到字典树，一个节点表示一条链下来的整个字符串，于是历史版本就只需要记录一个节点了
维护随机访问的话需要倍增，单次插入也要重新维护一遍倍增表，所以加点和查询都是
反思：栈结构与字典树的相似性
栈
如果在字典树上模拟栈，每次的加点和删点都只需要进行一次变动
基于栈先进先出的操作带来的前缀连续的结构，字典树上就不需要重新建一段低效的前缀
队列？
可行，删除队头只需要全局深度减一，维护一个变量就好了
依旧基于连续性
双端队列？
可行，但是仅限一头进两头出
随机改点删点？
不行，要么不再是一棵树，要么劳民伤财一次要建好多节点
总结
这样进行类比模拟搞可持久化的前提是前缀的连续性