A32402.数据中心能耗分析

"In the digital age, the real cost isn't just in data but in the energy that fuels the future."
Macw's AI startups caught up with the dividends of the times...

题目背景 (可略读)

随着大数据时代的到来，Macw 的数据中心已经成为企业和机构存储和处理海量数据的核心设施。然而，数据中心的能耗也随之急剧增加，这成为运营成本和环境保护的重要问题。为了优化数据中心的能耗管理，Macw 需要对特定时间段内的数据处理量进行分析和评估。

在数据中心内，服务器的运行状态和能耗密切相关。为了更好地进行能耗分析，运维团队需要计算某一时间段内的服务器处理任务的总能耗。经过分析，发现服务器处理任务的能耗可以通过处理数据量的立方和来近似估算。具体来说，如果某一时间段内服务器处理的数据量为 $A_1, A_2, A_3, \cdots, A_{n-1}, A_n$，那么该时间段内的总能耗可以近似表示为这些数据量的立方和。

然而，粗心的 Thomas 不小心篡改了几个数据，导致原本的处理算法无法正常工作。由于运维团队的负责人 Macw 比较忙，因此他特地找到了你。他相信聪明的你可以开发一款工具，能够快速计算任意时间段内服务器处理数据量的立方和，以便更好地进行能耗评估和优化。

题目要求

给定一个包含 $N$ 个元素的整型数组 $A$，表示数据中心在近 $N$ 天中每日服务器处理的数据量，其中 $A_i$ 表示第 $i$ 天数据中心所需要处理的数据量。你的任务是设计一个算法，可以快速的对 $A$ 数组的某一个区间进行 $M$ 次修改数值或统计立方和的操作。

Problem Credits: Macw07。

输入包含多行。

第一行输入两个整数 $N, M$，分别表示数组 $A$ 的大小和操作次数。

第二行包含 $N$ 个整数，第 $i$ 个整数表示第 $i$ 天数据中心所需要处理的数据量。

接下来的 $M$ 行，每一行为一种操作，格式为以下两种操作之一：

1. 操作一：$\color{ForestGreen}{\mathtt{1 \space L \space R \space K}}$，表示对数组 $A$ 在 $[L, R]$ 区间内的每一项元素加上数值 $K$。
2. 操作二：$\color{Navy}{\mathtt{2 \space L \space R}}$，表示查询数组 $A$ 在 $[L, R]$ 区间内的立方和。

对于更正式的数学表述如下：

1. 操作一：需要进行 $A_i \leftarrow A_i + K \quad \forall i \in [L, R]$ 操作。
2. 操作二：需要计算 $\sum_{i=L}^{R} A_i^3$ 的值。

对于每一个操作二，输出一行一个整数表示答案。

请注意，由于答案可能很大，输出答案时请对 $10^9+7$ 取模。对于一个负数取模，你应当保证取模的结果为非负整数。详情见样例二。

数据范围与约定：

本题共设有 $20$ 个测试点，满足以下要求：

测试点编号	数据范围
1-3	$1 \le N, M \le 10^2, \space R-L \le 10^2$
4-8	$1 \le N, M \le 5 \times 10^3, \space R-L \le 10^3$
9-20	各类特殊情况

对于 $100\%$ 的数据，保证 $1 \le N, M \le 10^5$。
对于 $100\%$ 的数据，保证 $-10^3 \le K \le 10^3$。
对于 $100\%$ 的数据，保证 $1 \le L \le R \le N$。
对于 $100\%$ 的数据，保证 $-10000 \le A_i \le 10000$。

样例解释：

对于样例一：

操作步骤	输入内容	操作要求	数列	输出结果	解释
0	<empty>	<empty>	1 2 3 4 5	<empty>	<empty>
1	2 3 3	查询区间 $[3, 3]$ 的立方和	1 2 3 4 5	27	$3^3 = 27$
2	2 1 5	查询区间 $[1, 5]$ 的立方和	1 2 3 4 5	225	$1^3 + 2^3 + 3^3 + 4^3 + 5^3 = 225$
3	1 1 1 -1	将区间 $[1, 1]$ 的数增加 $-1$	0 2 3 4 5	<empty>	<empty>
4	2 1 5	查询区间 $[1, 5]$ 的立方和	0 2 3 4 5	224	$0^3 + 2^3 + 3^3 + 4^3 + 5^3 = 224$
5	1 1 2 1	将区间 $[1, 2]$ 的数增加 $1$	1 3 3 4 5	<empty>	<empty>
6	2 1 5	查询区间 $[1, 5]$ 的立方和	1 3 3 4 5	244	$1^3 + 3^3 + 3^3 + 4^3 + 5^3 = 244$

对于样例二的第一个操作：

在没有取模的情况下，程序应该输出 $-1000$，但根据题目要求，为了保证答案的一致性，不应该直接输出 $-1000$ 对 $10^9+7$ 的结果，这会导致程序输出负数结果。对于所有负数的结果，应当在数字取模的基础上加上 $10^9+7$ 并再次对 $10^9+7$ 取模。