#P5602. Hdu4438 To the moon

    ID: 4603 传统题 1001ms 512MiB 尝试: 29 已通过: 7 难度: 7 上传者: 标签>数据结构CF2300可持久化线段树可持久化数据结构

Hdu4438 To the moon

To the moon

题目来源

题目描述

给定一个长度为 nn 的整数数组,初始时间戳为 00。依次执行以下操作。

  • C l r d。将当前数组中下标 ll 至 rr 的每项加上 dd,时间戳增加 11,并保存更新后的版本。
  • Q l r。查询当前版本中下标 ll 至 rr 的元素和。
  • H l r t。查询时间戳 tt 对应版本中下标 ll 至 rr 的元素和。查询不改变当前时间。
  • B t。将数组还原为时间戳 tt 的版本,当前时间戳也回到 tt。从该版本继续更新,之后的时间戳按新的更新顺序产生。

输入格式

有多组数据,读至文件结束。每组先输入两个整数 n,mn,m,再读入 nn 个初始值和 mm 条操作。操作按行给出。

1≤n,m≤1051\le n,m\le10^5,初始值的绝对值不超过 10910^9。所有区间均满足 1≤l≤r≤n1\le l\le r\le n,且 ∣d∣≤104\lvert d\rvert\le10^4。题目保证操作合法,回退不会跳到未来。

输出格式

按顺序为每个 Q 或 H 操作输出一行整数。相邻两组数据的输出之间留一个空行。

样例 1

10 5
1 2 3 4 5 6 7 8 9 10
Q 4 4
Q 1 10
Q 2 4
C 3 6 3
Q 2 4

2 4
0 0
C 1 1 1
C 2 2 -1
Q 1 2
H 1 2 1
4
55
9
15

0
1