#XDS203. 阶梯修改

阶梯修改

题目描述

你需要维护一个长度为 nn 的整数数组,支持两种操作:

  1. 将区间 [a,b][a,b] 内的元素进行阶梯加法操作:将第一个位置加 11,第二个位置加 22,依此类推,第 kk 个位置加 kk
  2. 查询区间 [a,b][a,b] 的元素之和。

输入格式

第一行包含两个整数 n,qn,q,表示数组长度和操作次数。

第二行包含 nn 个整数 t1,t2,,tnt_1,t_2,\dots,t_n,表示初始数组。

接下来 qq 行,每行一个操作,格式如下:

  • 1 a b:表示对区间 [a,b][a,b] 执行阶梯加法操作。
  • 2 a b:表示查询区间 [a,b][a,b] 的和。

输出格式

对于每个查询操作,输出一行一个整数,表示对应区间的和。

5 6
0 0 0 0 0
1 1 4
2 1 5
1 2 4
2 2 5
1 2 5
2 1 5
10
15
26

数据规模与约定

  • 对于 100%100\% 的数据,1n,q2×1051 \le n,q \le 2 \times 10^51ti1061 \le t_i \le 10^61abn1 \le a \le b \le n