P1022：TTM - To the moon

题目描述

给定一个长度为 $N$ 的数组 $\{A\}$，有 $4$ 种操作：

• C l r d：把区间 $[l,r]$ 中的每个数都加上 $d$，并将当前时间戳加 $1$。
• Q l r：查询当前时间戳下区间 $[l,r]$ 中所有数的和。
• H l r t：查询时间戳 $t$ 下区间 $[l,r]$ 中所有数的和。
• B t：把当前时间戳回退到 $t$。

所有操作均合法，初始时间戳为 $0$。

输入输出格式

输入

第一行两个正整数 $N, M$，表示数组长度和操作个数。

第二行包含 $N$ 个整数，表示数组 $\{A\}$。

接下来 $M$ 行，每行格式为 C l r d、Q l r、H l r t 或 B t，表示一次操作。

输出

对于每个 Q l r 或 H l r t 操作，输出一行一个整数表示答案。

样例

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

4
55
9
15

2 4
0 0
C 1 1 1
C 2 2 -1
Q 1 2
H 1 2 1

0
1

数据范围

• $1 \le N, M \le 10^5$
• $|A_i| \le 10^9$
• $1 \le l \le r \le N$
• $|d| \le 10^4$
• 初始时间戳为 $0$，且 B 操作不会访问未来时间戳