题目解析 我们先处理题目式子中的绝对值。 由于 ∑i=1N∣i−i∣×∣Ai−Ai∣=0\sum_{i=1}^N \vert i - i \vert \times \vert A_i - A_i \vert = 0∑i=1N ∣i−i∣×∣Ai −Ai ∣=0，所以原式可化为： (∑i=1N−1∑j=i+1N(j−i)×∣Ai−Aj∣)×2\left( \sum_{i=1}^{N-1}\sum_{j=i+1}^N (j - i) \times \vert A_i - A_j \vert \right) \times 2 (i=1∑N−1 j=i+1∑N (j−i)×∣Ai −Aj ∣)×2 注意到，本题 Ai(≤500)A_i(\le 500)Ai (≤500) 的范围较小，我们可以围绕此，对上式进行变换，从而高速计算。 对于上式，我们考虑枚举 iii，同时 令 cntxcnt_xcntx 代表 iii 之前所有元素中值 xxx 出现的次数； 令 sumxsum_xsumx 代表 iii 之前所有元素中值为 xxx 的下标之和； 那么可以将上式转化为： (∑i=1N∑x=0500(i×cntx−sumx)×∣Ai−x∣)×2\left( \sum_{i = 1}^{N} \sum_{x=0}^{500} (i \times cnt_x - sum_x) \times \vert A_i - x \vert \right) \times 2 (i=1∑N x=0∑500 (i×cntx −sumx )×∣Ai −x∣)×2 计算上式的时间复杂度为 O(N×max⁡(A))\mathrm{O}(N \times \max(A))O(N×max(A))，这样我们便可以高效地计算出答案。 AC 代码

提供另一种做法。 考虑枚举 AiA_iAi 和 jjj。于是我们只需要求： ∑k=1,Ak=AiN∣Ai−Aj∣×∣k−j∣\sum_{k=1, A_k=A_i}^N |A_i-A_j| \times |k-j| k=1,Ak =Ai ∑N ∣Ai −Aj ∣×∣k−j∣ 所以我们使用 vector<int> b[505] 记录每一个 AkA_kAk 所对应的 kkk. 不难发现，解决问题的瓶颈在于 ∣k−j∣|k-j|∣k−j∣ 的绝对值，所以我们在 b[A[i]] 中，二分找到第一个 kkk 满足 k≥jk \geq jk≥j. 然后设令贡献为 xxx，bib_ibi 的长度为 SiS_iSi ，推式子可以得到： 1. 对于 k<jk<jk<j，有： x=(j×k−(∑s=1k−1bs))×∣Ai−Aj∣x=(j \times k - (\sum_{s=1}^{k-1} b_s)) \times |A_i-A_j| x=(j×k−(s=1∑k−1 bs ))×∣Ai −Aj ∣ 2. 对于 k≥jk \geq jk≥j，有： x=((∑s=kSibs)−j×(Si−k))×∣Ai−Aj∣x=((\sum_{s=k}^{S_i} b_s)-j \times (S_i - k)) \times |A_i-A_j| x=((s=k∑Si bs )−j×(Si −k))×∣Ai −Aj ∣ 其中，求和部分可以使用前缀和优化。 这样，我们就得到了一个 O(nlog⁡nmax⁡(A))O(n \log n \max(A))O(nlognmax(A)) 的比 std 时间长、空间慢、更难写的代码。 Code: