求问一道可持久化数据结构的题该怎么解
  • 板块题目总版
  • 楼主1509cxt
  • 当前回复7
  • 已保存回复7
  • 发布时间2020/5/19 17:04
  • 上次更新2023/11/7 02:10:04
查看原帖
求问一道可持久化数据结构的题该怎么解
14487
1509cxt楼主2020/5/19 17:04

维护的是 单个整数元素(默认int范围内,初值是0,作为0号历史版本) 的多个历史版本。 有n个操作,是以下其中之一:

  1. 修改操作。 数据保证修改操作依据的历史版本是存在的:

    (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: 删除操作,不要求支持 删除 删除操作(即撤销删除操作)。支持了更好。

2020/5/19 17:04
加载中...