题解：P15546 「Stoi2037」七里香

题面

思路

$70$ 分做法

$70$ 分需要 $O(n^2)$ 实现，原式中有 $4$ 个变量肯定不能直接套，需要推式子。

\[\sum_{1\le l<r\le n}\sum_{l\le i<j\le r}[((j-1)k+a_j')-((i-1)k+a_i')]\]

发现 $l,r$ 不参与计算，对于一组 $i,j$，当且仅当 $l \in [1,i]$ 且 $r \in [j,n]$ 时会遍历到，因此 $i,j$ 会被遍历 $i \times (n-j+1)$ 次，于是可以将 $\sum_{1\le l<r\le n}\sum_{l\le i<j\le r}$ 转化为 $\sum_{1\le i < j\le n}i(n-j+1)$。

\[\begin{aligned} & \sum_{1 \leq l<r \leq n} \sum_{l \leq i<j \leq r}\left[\left((j-1) k+a_{j}^{\prime}\right)-\left((i-1) k+a_{i}^{\prime}\right)\right] \\ = & \sum_{1 \leq i<j \leq n} i(n-j+1) \left[\left((j-1) k+a_{j}^{\prime}\right)-\left((i-1) k+a_{i}^{\prime}\right)\right] \end{aligned}\]

此时只需要枚举 $i,j$，可以 $O(n^2)$ 完成，但是难以看出最大值，继续推。

\[\begin{aligned} & \sum_{1 \leq i<j \leq n} i(n-j+1) \left[\left((j-1) k+a_{j}^{\prime}\right)-\left((i-1) k+a_{i}^{\prime}\right)\right] \\ = & \sum_{1 \leq i<j \leq n} i(n-j+1) [(j-i)k+(a_{j}^{\prime}-a_{i}^{\prime})] \\ = & \sum_{1 \leq i<j \leq n} i(n-j+1) (j-i)k+ i(n-j+1)(a_{j}^{\prime}-a_{i}^{\prime}) \end{aligned}\]

此时，式子分为常数部分和变量部分，对于左半边，我们可以单独遍历求出。

对于右半部分，发现对于一对 $i,j$，$a_j^{\prime}$ 的权重为 $i(n-j+1)$，$a_i^{\prime}$ 的权重为 $-i(n-j+1)$。

因此，我们可以在遍历时计算各位置的权重并排序，与排序过后的 $a$ 数组一一对应相乘，并且加上常数部分，即可得出答案。

计算过程中可能出现范围超过 long long 的情况，可以用 int128 解决。

这个做法理论上是 $70$ 分，但是交上去似乎有 $80$ 分。

$100$ 分做法

依旧继续推式子。

对于常数部分，因为和 $k$ 没关系，所以先把 $k$ 提出。

\[\begin{aligned} & \sum_{1 \leq i<j \leq n} i(n-j+1) [(j-i)k+(a_{j}^{\prime}-a_{i}^{\prime})] \\ = & k \sum_{1 \leq i<j \leq n} i(n-j+1)(j-i) \end{aligned}\]

固定 $i$ 不变，对 $j$ 求和。令 $d=j-i$，则 $j=i+d$，$d \in [1,n-i]$，令 $m=n-i$。

将其代入算出 $i$ 的求和项。

\[\begin{aligned} & k \sum_{1 \leq i<j \leq n} i(n-j+1)(j-i) \\ = & k \sum_{j=i+1}^n i(n-j+1)(j-i) \\ = & k \sum_{d=1}^m i[n-(i+d)+1] \times d \\ = & k \sum_{d=1}^m i[(n-i+1)-d] \times d \\ = & k \sum_{d=1}^m i[(n-i+1)d-d^2] \\ = & k (\sum_{d=1}^m i + \sum_{d=1}^m [(n-i+1)d-d^2]) \\ = & k (\sum_{d=1}^m i + \sum_{d=1}^m (n-i+1)d- \sum_{d=1}^m d^2) \\ \end{aligned}\]

其中 $\sum_{d=1}^m i$ 可以单独算出，右半部分考虑运用等差数列求和公式以及平方和公式。

\[\begin{aligned} & \sum_{d=1}^m d=\frac{m(m+1)}{2} \\ & \sum_{d=1}^m d^2=\frac{m(m+1)(2m+1)}{6} \end{aligned}\]

代入原式。

\[\begin{aligned} & k (\sum_{d=1}^m i + \sum_{d=1}^m (n-i+1)d- \sum_{d=1}^m d^2) \\ = & k (\sum_{d=1}^m i + (n-i+1)\times \frac{m(m+1)}{2}-\frac{m(m+1)(2m+1)}{6}) \end{aligned}\]

至此，常数部分推导完毕，接下来看变量部分。

\[\sum_{1 \leq i<j \leq n} i(n-j+1)(a_{j}^{\prime}-a_{i}^{\prime})\]

从 $70$ 分的做法来说，我们的目标是求出对于 $1\le i \le n$ 中 $i$ 的权重。设 $i$ 的权重为 $w_i$，则我们的目标应该是求出以下式子。($i$ 和原式重复，所以这里使用 $p$)

\[\sum_{p=1}^n w_p \times a_p\]

首先，将原式的 $a_j^{\prime}$ 和 $a_i^{\prime}$ 分开。

\[\begin{aligned} & \sum_{1 \leq i<j \leq n} i(n-j+1)(a_{j}^{\prime}-a_{i}^{\prime}) \\ = & \sum_{1 \leq i<j \leq n} i(n-j+1)a_{j}^{\prime}- \sum_{1\le i < j\le n} i(n-j+1)a_{i}^{\prime} \end{aligned}\]

此时分 $2$ 种情况。

第 $1$ 种，$p=j$，此时 $i \in [1,p-1]$。

\[\begin{aligned} & \sum_{1 \leq i<j \leq n} i(n-j+1)a_{j}^{\prime} \\ = & \sum_{i=1}^{p-1} i(n-p+1)a_{p}^{\prime} \\ = & (n-p+1) \sum_{i=1}^{p-1} i\ a_{p}^{\prime} \\ = & (n-p+1) \times \frac{p(p-1)}{2} \sum_{i=1}^{p-1} \ a_{p}^{\prime} \end{aligned}\]

即 $w_p=(n-p+1)\times \frac{p(p-1)}{2}$.

第二种，$p=i$，此时 $j \in [p+1,n]$。

\[\begin{aligned} & -\sum_{1\le i < j\le n} i(n-j+1)a_{i}^{\prime} \\ = & -\sum_{j=p+1}^n p(n-j+1)a_{p}^{\prime} \\ = & -p \sum_{j=p+1}^n (n-j+1)a_{p}^{\prime} \\ \end{aligned}\]

令 $t=j-p$，则 $t \in [1,n-p]$，设 $m=n-p$。

\[\begin{aligned} & -p \sum_{j=p+1}^n (n-j+1)a_{p}^{\prime} \\ = & -p \sum_{t=1}^{m} (n-j+1)a_{p}^{\prime} \\ = & -p \sum_{t=1}^{m} (n-j+p-p+1)a_{p}^{\prime} \\ = & -p \sum_{t=1}^{m} (n-p+1-t)a_{p}^{\prime} \\ = & -p [\sum_{t=1}^{m} (n-p+1)-\sum_{t=1}^m t ]\sum_{j=p+1}^n a_{p}^{\prime} \\ = & -p [m(m+1)-\frac{m(m+1)}{2}]\sum_{j=p+1}^n a_{p}^{\prime} \\ = & -p \times \frac{m(m+1)}{2}\sum_{j=p+1}^n a_{p}^{\prime} \\ \end{aligned}\]

因此，$w_p= -p \times \frac{(n-p)(n-p+1)}{2}$。

将两种情况相加可得，$w_p=(n-p+1)\times \frac{p(p-1)}{2}-p \times \frac{(n-p)(n-p+1)}{2}$

经过化简可得，$w_p=\frac{p(n−p+1)(2p−n−1)}{2}$。

然后就和 $70$ 分的操作一样，将权重排序后与排序过的 $a$ 一一对应相乘，最后加上常数项，即为答案。

计算过程中可能出现范围超过 long long 的情况，可以用 int128 解决。

代码