T1 方差
观察式子：\(\large\sum\limits_{i=1}^{N-1} \sum\limits_{j=i+1}^{N}\left|A_{i}-A_{j}\right|^{2}=\sum\limits_{i=1}^{N-1} \sum\limits_{j=i+1}^{N}(A_{i}-A_{j})^{2}=\sum\limits_{i=1}^{N-1} \sum\limits_{j=i+1}^{N}(A_i^2-2A_iA_j+A_j^2)\)。
观察数据范围：\(2 \leq N \leq 3 \times 10^{5}\)。应该是 \(O(N)\) 的算法，结合原式中两个求和，可以想到枚举 \(i\)，前缀和处理 \(j\)。
具体地，因为 \(A_j\) 有两种不同次数，令 \(x_i=\large\sum\limits_{i+1}^NA_i\)，\(y_i=\large\sum\limits_{i+1}^NA_j^2\)。
所以 原式 \(=\large\sum\limits_{i=1}^{N-1} ((N-i)A_i^2-2A_ix_i+y_i)\)。
最后记得开 ll。
#include <cstdio>
#define int long long
const int MAXN = 3e5 + 5;
int n, a[MAXN], x, y, ans;
signed main () {
scanf("%lld", &n);
for (int i = 1; i <= n; i++) scanf("%lld", a + i);
for (int i = n; i; i--) {
if (i < n)
ans += (n-i)*a[i]*a[i] - 2*a[i]*x + y;
x += a[i], y += a[i]*a[i];
}
printf("%lld", ans);
return 0;
}