维护的是 单个整数元素(默认int范围内,初值是0,作为0号历史版本) 的多个历史版本。
有n个操作,是以下其中之一:
-
修改操作。
数据保证修改操作依据的历史版本是存在的:
(1)加:把 历史版本p 的这个元素加上x,产生新的历史版本。
(2)乘:把 历史版本p 的这个元素乘上x,产生新的历史版本。
(3)赋值:把 历史版本p 的这个元素赋值为x,产生新的历史版本。
(4)删除:把产生 历史版本p 的修改操作(设版本p那次修改依据的是版本q)删去,
之前依据版本p的修改操作 自动顺延成为 依据版本q进行的操作。
删除操作不产生新的历史版本。
2.查询历史版本p的元素数值。
以上每个操作要求 时间O(logn)或者O(1),空间暂时没有限制。
样例输入:
8个操作
①版本0 加2 //产生版本1:数值2
②版本1 赋值3 //产生版本2:数值3
③版本2 加2 //产生版本3:数值5
④版本3 乘2 //产生版本4:数值10
⑤查询版本3
⑥删除版本2对应的操作
//此时版本1:数值2, 版本2:不存在, 版本3:数值4, 版本4:数值8
⑦查询版本3
⑧查询版本4
样例输出:
5
4
8
PS:
删除操作,不要求支持 删除 删除操作(即撤销删除操作)。支持了更好。