题解

提供另一种做法。

考虑枚举 $A_i$ 和 $j$。于是我们只需要求：

$$\sum_{k=1, A_k=A_i}^N |A_i-A_j| \times |k-j|$$

所以我们使用 vector<int> b[505] 记录每一个 $A_k$ 所对应的 $k$.

不难发现，解决问题的瓶颈在于 $|k-j|$ 的绝对值，所以我们在 b[A[i]] 中，二分找到第一个 $k$ 满足 $k \geq j$.

然后设令贡献为 $x$，$b_i$ 的长度为 $S_i$，推式子可以得到：

1. 对于 $k<j$，有：

$$x=(j \times k - (\sum_{s=1}^{k-1} b_s)) \times |A_i-A_j|$$

2. 对于 $k \geq j$，有：

$$x=((\sum_{s=k}^{S_i} b_s)-j \times (S_i - k)) \times |A_i-A_j|$$

其中，求和部分可以使用前缀和优化。

这样，我们就得到了一个 $O(n \log n \max(A))$ 的比 std 时间长、空间慢、更难写的代码。

Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXN=2e5+25;
ll n,x,l,r,ans;
ll a[MAXN],sz[505];
vector<ll> b[505],pre[505];
inline ll abss(const ll &x){return x<0?-x:x;}
int main(){
    ios::sync_with_stdio(false);
    cin>>n;
    for(ll i=1;i<=n;i++){
        cin>>a[i];
        b[a[i]].emplace_back(i);
        sz[a[i]]++;
        if(pre[a[i]].empty()) pre[a[i]].emplace_back(i);
        else pre[a[i]].emplace_back(i+pre[a[i]].back());
    }
    for(ll i=1;i<=500;i++){
        if(sz[i]==0) continue;
        for(ll j=1;j<=n;j++){
            x=lower_bound(b[i].begin(),b[i].end(),j)-b[i].begin();
            if(x) ans+=(j*x-pre[i][x-1])*abss(i-a[j]);
            if(x<sz[i]) ans+=(pre[i].back()-(x?pre[i][x-1]:0)-j*(sz[i]-x))*abss(i-a[j]);
        }
    }
    cout<<ans;
    return 0;
}