haar_lib/typical/double_sigma/max.rs
1//! 2要素の最大値の総和
2
3/// 2要素の最大値の総和
4///
5/// **Time complexity** $O(|a| \log |a|)$
6///
7/// # Explanation
8/// $$\bigstar = \sum_{1 \le i \le N-1} \sum_{i+1 \le j \le N} \max(a_i, a_j)$$
9///
10/// $f(i, j) = \max(a_i, a_j)$は可換なので、$a$を昇順にソートされているものとする。
11///
12/// このとき、$a_i$が最大値となる$(i,j)$ペアがいくつあるかを考えると、
13/// これは、$i-1$個であるので、
14/// $$\bigstar = \sum_{1 \le i \le N} (i-1)a_i$$
15pub fn sum_of_sum_of_max(mut a: Vec<i64>) -> i64 {
16 a.sort();
17 a.into_iter().enumerate().map(|(i, x)| x * i as i64).sum()
18}