CSES1736 多项式查询
#CS1736. 多项式查询
多项式查询
题目背景
翻译自 CSES-1736 题。
题目描述
你的任务是维护一个包含 n 个值的数组，并高效地处理以下几种类型的查询：
-
对区间 [a,b] [a,b][a,b] 中的值进行多项式增加：将区间中第一个值增加 1，第二个值增加 2，第三个值增加 3，以此类推。
-
计算区间 [a,b][a,b][a,b] 中的值的和。
输入格式
第一行包含两个整数 n 和 q：分别表示数组的大小和查询的数量。
第二行包含 n 个整数 t1,t2,…,tnt_1,t_2,…,t_nt1,t2,…,tn：表示数组的初始内容。
接下来有 q 行，每行描述一个查询。查询的格式有两种：
-
1 a b：表示将区间 [a,b][a,b][a,b] 中的第一个值增加 1，第二个值增加 2，第三个值增加 3，以此类推。
-
2 a b：表示计算区间 [a,b][a,b][a,b] 中的值的和。
输出格式
对于每个类型为 2 的查询，输出该区间内值的和。
样例
5 3
4 2 3 1 7
2 1 5
1 1 5
2 1 5
17
32
说明/提示
1≤ti≤1061 \leq t_i \leq 10^61≤ti≤106；