haar_lib/typical/double_sigma/
difference.rs

1//! 2要素の差の絶対値の総和
2
3/// 2要素の差の絶対値の総和
4///
5/// **Time complexity** $O(|a| \log |a|)$
6///
7/// # Problems
8/// - <https://atcoder.jp/contests/abc186/tasks/abc186_d>
9///
10/// # Explanation
11/// $$\bigstar = \sum_{1 \le i \le N-1} \sum_{i+1 \le j \le N} |a_i - a_j|$$
12///
13/// $f(i, j) = |a_i - a_j|$は可換なので、$a$を降順にソートされているものとする。
14///
15/// このとき、$a_i \ge a_j (i \lt j)$なので、絶対値は外してよく、
16///
17/// $$
18/// \begin{aligned}
19/// \bigstar &= \sum_{1 \le i \le N-1} \sum_{i+1 \le j \le N} (a_i - a_j) \\\\
20/// &= \sum_{1 \le i \le N-1} ((N-i) * a_i - \sum_{i+1 \le j \le N} a_j)
21/// \end{aligned}
22/// $$
23///
24/// 各$a_i$が何回だけ加減算されているかを考えると、
25/// シグマ内の第一項から$N-i$回足して、第二項から$i-1$回引いているので、
26/// $$\bigstar = \sum_{1 \le i \le N} ((N-i)-(i-1))a_i$$
27pub fn sum_of_sum_of_difference(mut a: Vec<i64>) -> i64 {
28    let mut ret = 0;
29    let n = a.len();
30    a.sort();
31
32    for (i, x) in a.into_iter().enumerate() {
33        ret += x * (i as i64 * 2 + 1 - n as i64);
34    }
35
36    ret
37}
haar_lib/typical/double_sigma/difference.rs

haar_lib/typical/double_sigma/
difference.rs
