瑟班守护者莎利雅与护教军_

「瑟班是我们的家乡，我不会让它落入孽物大军手中。」　 —— 莎利雅

瑟班守护者莎利雅领导着一支护教军。这支护教军的兵力守卫在塞班的各个角落。

瑟班大教廷中有 n 个地点，编号为 $1 \sim n$ 。这 n 个地点排成一列，第 i 个地点有 d_i 的危险值，并有值为 f_i 的兵力分布在这里。
为了更好的应战，每个地点所分布的兵力会根据每个地点危险值的变化而变化。更形式化地，第 i 个地点的兵力值 f_i 可以根据以下公式计算：
$f_i = \max(d_i, \min(\max^{i-1}_{j=1} d_j, \max^{n}_{k=i+1} d_k))$
特别地，当 i=1 时， $\displaystyle\max^{i-1}_{j=1} d_j$ 项值为 0 ；当 i=n 时， $\displaystyle\max^{n}_{k=i+1} d_k$ 项值也为 0 。
现在，莎利雅作为瑟班的守护者、月主教护卫部队领袖，遇到了一些难题。她需要处理下级提供的情报，并能随时获取自己已分配的总兵力，或者了解哪些位置兵力足够、哪些位置兵力不足。

更形式化地，我们将这一系列操作分为以下三种：

1. 莎利雅需要知道已分配的总兵力：询问所有地点的兵力值总和。即 $\displaystyle \sum_{i=1}^{n} f_i$ 。

2. 莎利雅需要知道某个区间内哪些位置兵力充足：编号在 [l, r] 的地点中兵力值大于等于 v 的个数。即 $\displaystyle \sum_{i=l}^{r} [f_i \ge v]$ 。

3. 莎利雅获得情报：地点 i 的危险值增加了 v 。由于乱战愈发激烈，每个地区的危险值不会降低。也就是说，v 是一个非负整数。

莎利雅正忙于跟莉莲娜维斯交战，所以只好请你来帮助她了！

第一行包含两个整数 n, m ，表示地点数及操作数。
第二行包含 n 个非负整数，第 i 个数表示初始时地点 i 的危险值。
接下去 m 行，每行若干个整数，表示一次操作。其中第一个数 op 表示操作类别。
- 当 op = 1 时，表示莎利雅得到了情报。你需要输出一个答案。
- 当 op = 2 时，后面跟着三个整数 l, r, v，表示莎利雅想知道区间 [l, r] 内哪些位置兵力值大于等于 v 。你需要输出一个答案。
- 当 op = 3 时，后面跟着两个整数 x, v，表示莎利雅获得了一个情报，地点 x 的危险值会加上 v 。

说明

- 初始时，危险值序列 {d_i} 为 {10, 5, 9, 5} ，可以计算出兵力值序列 {f_i} 为 {10, 9, 9, 5} 。
- 第一个操作为 1 操作，询问兵力值序列 {f_i} 的和，为 10 + 9 + 9 + 5 = 33 。
- 第二个操作为 3 操作，将 3 号地点的危险值升高 2 。之后危险值序列 {d_i} 变为 {10, 5, 11, 5} ，可以计算出兵力值序列 {f_i} 为 {10, 10, 11, 5} 。
- 第三个操作为 2 操作，询问兵力值序列 {f_i} 中区间 [1, 4] 内兵力值大于等于 10 的地点个数。其中 1, 2, 3 号地点满足条件，答案为 3 。

1 ≤ n, m ≤ 3 x 10⁵
0 ≤ d_i, v ≤ 10⁹
1 ≤ x, l, r ≤ n
保证任一时刻所有位置的危险值和兵力值均在带符号 64 位整数范围内。

你可以认为莎利雅的兵力源源不断，没有上限。

最后，在莉莲娜维斯的要挟下，莎利雅为了依尼翠，决定违背自己的誓言，破坏了狱窖，释放出大天使艾维欣与恶魔棘泽边。莉莲娜维斯摧毁了棘泽边完成了她的目标，依尼翠也因艾维欣的归来而开始恢复繁荣。但，这样的和平也只能维持一小段时间……

瑟班守护者莎利雅与护教军

输入描述:

输出描述:

输入

输出

说明

备注:

问题信息

热门推荐

相关试题