T3 魔法少女(kisara)
我们先初步化简一下原式，即：
\(\texttt{ans}=\sum\limits_{l'=l}^r\sum\limits_{r'=l'}^r(\sum\limits_{i=l'}^{r'}a_i)^2+\sum\limits_{l'=l}^r\sum\limits_{r'=l'}^r(r-l+2)(r'-l')a_{l'}a_{r'}\)
将式子中后面那一堆中的 \(r - l + 2\) 提出来，即：
\(\texttt{ans}=\sum\limits_{l'=l}^r\sum\limits_{r'=l'}^r(\sum\limits_{i=l'}^{r'}a_i)^2+(r-l+2)\sum\limits_{l'=l}^r\sum\limits_{r'=l'}^r(r'-l')a_{l'}a_{r'}\)
我们单独分析一下 \(\texttt{ans}\) 前面那一堆，将平方拆开，会变成：
\(\texttt{ans2} = \sum\limits_{l'=l}^r\sum\limits_{r'=l'}^r(\sum\limits_{l'}^{r'}a_i)^2=\sum\limits_{l'=l}^r\sum\limits_{r'=l'}^r(\sum\limits_{l'}^{r'}a_i^2+2\times\sum\limits_{l'\leq i<r\leq r'}a_ia_j)\)
想象一下最后去掉前两个 \(\sum\) 后合并同类项，那么
对于 \(a_i^2\) 的系数：\((i-l+1)\times(r-i+1)\)
对于 \(a_ia_j(i<j)\) 的系数：\(2\times (i-l+1)\times (r-j+1)\)
那么我们就可以重写一下 \(\texttt{ans2}\)，即：
\(\texttt{ans2} = \sum\limits_{i = l}^r (i - l + 1)(r - i + 1)a_i^2 + \sum\limits_{l\leq i < j\leq r}2(i - l + 1)(r - j + 1)a_ia_j\)
观察 \(\texttt{ans2}\)，我们发现现在的时间复杂度瓶颈还是在于后面那一堆，那我们接下来再来单独分析一下 \(\texttt{ans2}\) 后面那一堆。
我们想要让后面的那一堆达到类似于 \((\sum\limits_{i = l}^rx_ia_i)\times (\sum\limits_{i = l}^ry_ia_i)\) 的效果。
由于后面那一堆的式子的系数为 \(2\)，所以我们可以尝试把它写开：
\(\texttt{ans3} = \sum\limits_{l\leq i < j\leq r}(i - l + 1)(r - j + 1)a_ia_j + \sum\limits_{l\leq i < j\leq r}(i - l + 1)(r - j + 1)a_ia_j\)
发现我们现在只有 \(i < j\) 的情况，没有 \(j < i\) 的情况，我们可以先暂时将后面那一堆的 \(i\) 和 \(j\) 两个变量交换一下：
\(\texttt{ans3} = \sum\limits_{l\leq i < j\leq r}(i - l + 1)(r - j + 1)a_ia_j + \sum\limits_{l\leq j < i\leq r}(j - l + 1)(r - i + 1)a_ia_j\)
很显然，我们发现，虽然有了 \(i < j\) 和 \(j < i\) 的情况，但是前面的系数对不上，所以我们可以将后面那个式子转化一下：
\(\texttt{ans3} = \sum\limits_{l\leq i < j\leq r}(i - l + 1)(r - j + 1)a_ia_j + \sum\limits_{l\leq j < i\leq r}[i - l + 1 - (i - j)][r - j + 1 - (i - j)]a_ia_j\)
设 \(\texttt{ans4}\) 为后面那一堆，把后面的化开：
\(\texttt{ans4} = \sum\limits_{l\leq j < i\leq r}(i - l + 1)(r - j + 1)a_ia_j + \sum\limits_{l\leq j < i\leq r}(i - j)^2a_ia_j - \sum\limits_{l\leq j < i\leq r}(i - j)(r - l + i - j + 2)a_ia_j\)
第一项不就是我们想要的东西吗？
我们发现，\(\texttt{ans4}\) 的最后一项看起来非常的恶心，但是我们发现第二项的系数里有 \(i - j\) 和前面的 \(i - j\) 共同组成一个 \((i - j)^2\)，还有 \(r - l + 2\) 与前面的 \(i - j\) 共同组成一个 \((r - l + 2)(i - j)\)，即：
\(\texttt{ans5} = \sum\limits_{l\leq j < i\leq r}(i - j)^2a_ia_j + \sum\limits_{l\leq j < i\leq r}(r - l + 2)(i - j)a_ia_j\)
那么 \(ans5\) 的第一项和 \(ans4\) 的第二项就可以消掉了。
将 \(\texttt{ans5}\) 代进 \(\texttt{ans4}\) 为：
\(\texttt{ans4} = \sum\limits_{l\leq j < i\leq r}(i - l + 1)(r - j + 1)a_ia_j - \sum\limits_{l\leq j < i\leq r}(r - l + 2)(i - j)a_ia_j\)
非常简洁！
继续带回 \(\texttt{ans3}\)，即：
\(\texttt{ans3} = \sum\limits_{l\leq i < j\leq r}(i - l + 1)(r - j + 1)a_ia_j + \sum\limits_{l\leq j < i\leq r}(i - l + 1)(r - j + 1)a_ia_j - \sum\limits_{l\leq j < i\leq r}(r - l + 2)(i - j)a_ia_j\)
我们发现，前面那两项合并之后就是 \(\sum\limits_{i = l}^r\sum\limits_{j = l}^r(i - l + 1)(r - j + 1)a_ia_j - \sum\limits_{i = l}^r(i - l + 1)(r - i + 1)a_i^2\)
相当于就是缺少了 \(i = j\) 的情况，只需要抠掉就是上面的式子了。
继续带回 \(\texttt{ans3}\)，即：
\(\texttt{ans3} = \sum\limits_{i = l}^r\sum\limits_{j = l}^r(i - l + 1)(r - j + 1)a_ia_j - \sum\limits_{i = l}^r(i - l + 1)(r - i + 1)a_i^2 - \sum\limits_{l\leq j < i\leq r}(r - l + 2)(i - j)a_ia_j\)
再带回 \(\texttt{ans2}\)，即：
\(\texttt{ans2} = \sum\limits_{i = l}^r\sum\limits_{j = l}^r(i - l + 1)(r - j + 1)a_ia_j - \sum\limits_{i = l}^r(i - l + 1)(r - i + 1)a_i^2 - \sum\limits_{l\leq j < i\leq r}(r - l + 2)(i - j)a_ia_j + \sum\limits_{i = l}^r (i - l + 1)(r - i + 1)a_i^2\)
第二项和第四项又可以消掉哩！\(\texttt{ans2}\) 就变成了：
\(\texttt{ans2} = \sum\limits_{i = l}^r\sum\limits_{j = l}^r(i - l + 1)(r - j + 1)a_ia_j - \sum\limits_{l\leq j < i\leq r}(r - l + 2)(i - j)a_ia_j\)
最后再带回 \(\texttt{ans}\) 就是：
\(\texttt{ans} = \sum\limits_{i = l}^r\sum\limits_{j = l}^r(i - l + 1)(r - j + 1)a_ia_j - \sum\limits_{l\leq j < i\leq r}(r - l + 2)(i - j)a_ia_j + (r-l+2)\sum\limits_{l'=l}^r\sum\limits_{r'=l'}^r(r'-l')a_{l'}a_{r'}\)
重写一下 \(\texttt{ans}\) 的第二项和第三项：
\(\texttt{ans} = \sum\limits_{i = l}^r\sum\limits_{j = l}^r(i - l + 1)(r - j + 1)a_ia_j - (r - l + 2)\sum\limits_{l\leq j < i\leq r}(i - j)a_ia_j + (r-l+2)\sum\limits_{l\leq i\leq j\leq r}(j - i)a_{i}a_{j}\)
第二项中，发现当 \(i = j\) 时，\(i - j\) 直接等于 \(0\) 了，对答案没有影响，我们可以直接将 \(i = j\) 的情况放进去：
\(\texttt{ans} = \sum\limits_{i = l}^r\sum\limits_{j = l}^r(i - l + 1)(r - j + 1)a_ia_j - (r - l + 2)\sum\limits_{l\leq j \leq i\leq r}(i - j)a_ia_j + (r-l+2)\sum\limits_{l\leq i\leq j\leq r}(j - i)a_{i}a_{j}\)
交换第二项的 \(i\) 和 \(j\) 得：
\(\texttt{ans} = \sum\limits_{i = l}^r\sum\limits_{j = l}^r(i - l + 1)(r - j + 1)a_ia_j - (r - l + 2)\sum\limits_{l\leq i \leq j\leq r}(j - i)a_ia_j + (r-l+2)\sum\limits_{l\leq i\leq j\leq r}(j - i)a_{i}a_{j}\)
然后第二项和第三项就又可以消掉啦！
最后 \(\texttt{ans}\) 就是 \(\sum\limits_{i = l}^r\sum\limits_{j = l}^r(i - l + 1)(r - j + 1)a_ia_j\)
重写一下 \(\texttt{ans}\) 就是：
\(\texttt{ans} = [\sum\limits_{i = l}^r(i - l + 1)a_i][\sum\limits_{j = l}^r(r - j + 1)a_j]\)
只需要线段树维护 \(i\times a_i\) 之和和 \(a_i\) 之和即可，此步骤支持区间修改和区间求和。
时间复杂度 \(\mathcal{O}(q\log n)\)
标签：limits,sum,texttt,kirasa,leq,ans,ia From： https://www.cnblogs.com/wwlwakioi/p/16755462.html