#P5602. Hdu4438 To the moon
Hdu4438 To the moon
To the moon
题目描述
给定一个长度为 的整数数组,初始时间戳为 。依次执行以下操作。
C l r d。将当前数组中下标 至 的每项加上 ,时间戳增加 ,并保存更新后的版本。Q l r。查询当前版本中下标 至 的元素和。H l r t。查询时间戳 对应版本中下标 至 的元素和。查询不改变当前时间。B t。将数组还原为时间戳 的版本,当前时间戳也回到 。从该版本继续更新,之后的时间戳按新的更新顺序产生。
输入格式
有多组数据,读至文件结束。每组先输入两个整数 ,再读入 个初始值和 条操作。操作按行给出。
,初始值的绝对值不超过 。所有区间均满足 ,且 。题目保证操作合法,回退不会跳到未来。
输出格式
按顺序为每个 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