【模板】可持续化线段树 1

【模板】可持续化线段树 1

作业已超过截止时间,您无法递交本题目。

题目描述

《去月球》是 \(2011\) 年 \(11\) 月发布的一款独立游戏,是一款角色扮演冒险游戏,由 \(\text{RPG~Maker}\)制造商提供支持。

登月的前提是基于一项技术,这项技术允许我们永久性地重建对垂死的人的记忆。在这个问题中,我们将给您一个机会,实现幕后的逻辑。

一个长度为 \(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\)

输入格式,一行 \(N\) 和 \(M\),接下来 \(M\) 行每行一个操作

输出格式:对每个查询输出一行表示答案

格式

输入格式

输入第 \(1\) 行 \(N,M\),表示 \(N\) 个数,\(M\) 个询问;

输入第 \(2\) 行为 \(N\) 个数 \(A[i]\);

接下来是 \(M\) 个操作,如题意所述。

输出格式

针对每个询问输出相应的值。

样例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

限制

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

线段树 / 主席树练习

未认领
状态
已结束
题目
4
开始时间
2022-09-06 22:00
截止时间
2022-09-13 23:59
可延期
504.0 小时