T8 - 数据中心能耗分析
题目链接跳转：点击跳转
本文仅针对对线段树有一定了解且并且有着较高的程序设计能力的选手。本文的前置知识如下：
1. 线段树的构造与维护 - 可以参考文章 浅入线段树与区间最值问题。
2. 初中数学 - 完全平方和公式和完全立方和公式。
3. 取模 - 之如何保证对所有整数取模后的结果为非负整数 - 可以参考本题的 说明/提示 部分。
> 原本出题的时候我并不知道这道题在许多 OJ 上是有原题的，so sad（下次再改进）。
题目本身应该非常好理解，就是给定一个数组，让你设计一个程序，对程序进行区间求立方和和区间修改的操作。但本题的数据量比较大，N,MN, MN,M 最大可以达到 10510^5105，对于每一次修改和查询都是 O(N)O(N)O(N) 的时间复杂度，显然用暴力的方法时间复杂度绝对会超时，最高会到 O(N2∗M)O(N^2 * M)O(N2∗M) （大概需要 115115115 天的时间才可以搞定一个测试点）。当看到区间查询和维护操作的时候，不难想到用线段树的方法，在线段树中，单次操作的时间复杂度约为 O(log2N)O(log_2 N)O(log2 N)，即使当 NNN
非常大的时候线段树也可以跑得飞起。
解题思路
不得不说，这是一道比较恶心的线段树区间维护的题目。不光写起来比较费劲，而且维护操作运算量比较大。稍有不慎就会写歪（因此写这道题的时候要集中注意力，稍微一个不起眼的问题就容易爆 000）。
本题的主要难点就是对一个区间内进行批量区间累加的操作。很容易就想到跟完全立方公式的联系：(a+b)3=a3+3a2b+3ab2+b3(a+b)^3 = a^3 +3a^2b + 3ab^2 + b^3(a+b)3=a3+3a2b+3ab2+b3。区间累加操作也只不过是对区间的所有数字都进行该操作，并对所有操作的结果求和就是该区间进行操作后的立方和。化简可得：
ANS=∑i=1n(ai+x)3=(a1+b)3+(a2+b)3+⋯+(an+b)3=(a13+3a12b+3a1b2+b3)+(a23+3a22b+3a2b2+b3)+⋯+(an3+3an2b+3anb2+b3)=(a13+a23+⋯+an3)+3b(a12+a22+⋯+an2)+3b2(a1+a2+⋯+an)+nb3=∑i=1nai3+3b∑i=1nai2+3b2∑i=1nai+nb3\begin{align} \mathtt{ANS} &= \sum_{i=1}^{n}{(a_i+x)^3}\\ &= (a_1+b)^3+(a_2+b)^3+ \cdots + (a_n+b)^3 \\
&= (a_1^3 + 3a_1^2b + 3a_1b^2 + b^3) + (a_2^3 + 3a_2^2b + 3a_2b^2 + b^3) + \cdots + (a_n^3 + 3a_n^2b + 3a_nb^2 + b^3) \\ &= (a_1^3 + a_2^3 + \cdots + a_n^3) + 3b(a_1^2 + a_2^2 + \cdots + a_n^2) + 3b^2(a_1 + a_2 + \cdots + a_n) + nb^3 \\ &= \sum_{i=1}^{n}{a_i^3} + 3b\sum_{i=1}^{n}{a_i^2} +
3b^2\sum_{i=1}^{n}{a_i} + nb^3 \end{align} ANS =i=1∑n (ai +x)3=(a1 +b)3+(a2 +b)3+⋯+(an +b)3=(a13 +3a12 b+3a1 b2+b3)+(a23 +3a22 b+3a2 b2+b3)+⋯+(an3 +3an2 b+3an b2+b3)=(a13 +a23 +⋯+an3 )+3b(a12 +a22 +⋯+an2 )+3b2(a1 +a2 +⋯+an )+nb3=i=1∑n ai3 +3bi=1∑n ai2 +3b2i=1∑n ai +nb3
综上所述，我们只需要用线段树维护三个字段，分别是区间的立方和、区间的平方和以及区间和。在维护平方和的过程中与维护立方和类似，根据完全平方公式 (a+b)2=a2+2ab+b2(a+b)^2 = a^2 + 2ab + b^2(a+b)2=a2+2ab+b2。经过累加和化简可得：
ANS=∑i=1n(ai+x)2=(a1+b)2+(a2+b)2+⋯+(an+b)2=(a12+2a1b+b2)+(a22+2a2b+b2)+⋯+(an2+2anb+b2)=(a12+a22+⋯+an2)+2b(a1+a2+⋯+an)+nb2=∑i=1nai2+2b∑i=1nai+nb2\begin{align} \mathtt{ANS} &= \sum_{i=1}^{n}{(a_i+x)^2}\\ &= (a_1+b)^2 + (a_2+b)^2 + \cdots + (a_n+b)^2 \\ &= (a_1^2 + 2a_1b + b^2) + (a_2^2 + 2a_2b + b^2)
+ \cdots + (a_n^2 + 2a_nb + b^2) \\ &= (a_1^2 + a_2^2 + \cdots + a_n^2) + 2b(a_1 + a_2 + \cdots + a_n) + nb^2 \\ &= \sum_{i=1}^{n}{a_i^2} + 2b\sum_{i=1}^{n}{a_i} + nb^2 \end{align} ANS =i=1∑n (ai +x)2=(a1 +b)2+(a2 +b)2+⋯+(an +b)2=(a12 +2a1 b+b2)+(a22 +2a2 b+b2)+⋯+(an2 +2an b+b2)=(a12 +a22 +⋯+an2
)+2b(a1 +a2 +⋯+an )+nb2=i=1∑n ai2 +2bi=1∑n ai +nb2
以上三个字段可以在构造线段树的时候一并初始化，之后的每次更新直接修改懒标记就可以了。一切都交给 push_down() 函数。在每次区间查询和修改之前都进行懒标记下放操作，对区间进行维护。具体维护操作如下：
注意事项
1. 请注意取模，为了保证答案正确性，请在每一步操作的时候都对结果取模。
2. 开 long long，不然的话只能过前三个测试点（出题人还是挺好的，留了三个小的测试点骗粉）。
3. 在维护立方和、平方和以及和的时候，请注意维护的顺序。应当先维护立方和，再维护平方和，最后再维护区间总和。
4. 注意线段树数组的大小，应当为 4×N4 \times N4×N。
5. 建议使用读入优化，直接使用 cin 的效率比 std 慢约 100%100\%100% 。
时间复杂度
线段树单次查询和修改的复杂度约为 O(log2N)O(log_2 N)O(log2 N)，初始化的时间复杂度为 Θ(N)\Theta(N)Θ(N)，因此本代码的整体时间复杂度可以用多项式 Θ(N+M⋅log2(N))\Theta(N + M \cdot log_2(N))Θ(N+M⋅log2 (N)) 来表示，整体代码的时间复杂度就为 O(M⋅log2(N))O(M \cdot log_2(N))O(M⋅log2 (N))。在极限数据下，程序只需要 160ms160ms160ms 就可以完成暴力一整年所需的工作。
代码实现
1. 代码使用了宏定义，方便后期进行调式。
2. 以下代码与普通的线段树无太大区别，但请着重关注 push_down() 下放操作。
以下是本题的 Python 代码，但由于 Python 常数过大，没有办法通过所有的测试点：
