Double Sum の解説

iを固定して考える。

Aj - Ai < 0 のものは考えなくてよいので、Aiより大きいものについて考える。

Additiveな2つのセグ木を用意する。

• 区間の個数を数えられるもの
• 区間の和を計算できるもの

を計算できれば、sum(Ai..) - count(Ai..) * Ai を左から順に計算できるのでこれが答えとなる。

fn main() {
    input! {
        n: usize,
        a: [usize; n]
    }
    let comp = CoordinateCompression::new(&a);
    let mut count = Segtree::<M>::new(comp.len());
    let mut sum = Segtree::<M>::new(comp.len());
    for &num in a.iter() {
        let id = comp.get(num).unwrap();
        let pre = count.get(id);
        count.set(id, pre + 1);
        let pre = sum.get(id);
        sum.set(id, pre + num);
    }
    let mut ans = 0;
    for &num in a.iter() {
        let id = comp.get(num).unwrap();
        let pre = count.get(id);
        count.set(id, pre - 1);
        let pre = sum.get(id);
        sum.set(id, pre - num);
        let ss = sum.prod(id..);
        let cc = count.prod(id..);
        ans += ss - cc * num;
    }
    println!("{}", ans);
}