HDU4348 - 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$ 。

所有操作均合法 。

ps：刚开始时时间戳为 $0$

输入格式

无

输出格式

数据保证：$1\le N,M\le 10^5$，$|A_i|\le 10^9$，$1\le l \le r \le N$，$|d|\le10^4$。在刚开始没有进行操作的情况下时间戳为 $0$，且保证 B 操作不会访问到未来的时间戳。

输入输出样例 #1

输入 #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

输出 #1

4
55
9
15

输入输出样例 #2

输入 #2

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

输出 #2

0
1