题目背景

翻译自 CSES-1736 题。

题目描述

你的任务是维护一个包含 $n$ 个值的数组，并高效地处理以下几种类型的查询：

1. 对区间 $[a,b]$ 中的值进行多项式增加：将区间中第一个值增加 $1$，第二个值增加 $2$，第三个值增加 $3$，以此类推。
2. 计算区间 $[a,b]$ 中的值的和。

输入格式

第一行包含两个整数 $n$ 和 $q$：分别表示数组的大小和查询的数量。

第二行包含 $n$ 个整数 $t_1,t_2,\ldots,t_n$：表示数组的初始内容。

接下来有 $q$ 行，每行描述一个查询。查询的格式有两种：

• 1 a b：表示将区间 $[a,b]$ 中的第一个值增加 $1$，第二个值增加 $2$，第三个值增加 $3$，以此类推。
• 2 a b：表示计算区间 $[a,b]$ 中的值的和。

输出格式

对于每个类型为 2 的查询，输出该区间内值的和。

样例

5 3
4 2 3 1 7
2 1 5
1 1 5
2 1 5

17
32

数据范围

• $1 \le n,q \le 2 \cdot 10^5$
• $1 \le t_i \le 10^6$
• $1 \le a \le b \le n$