inversion/
lib.rs

1use std::{
2    iter::{Product, Sum},
3    ops::{Add, AddAssign},
4};
5
6pub trait Inversion {
7    fn inversion<I: Add<I> + for<'a> AddAssign<&'a I> + Sum<I> + Product<I>>(
8        &self,
9    ) -> I;
10}
11
12impl<T: Ord> Inversion for [T] {
13    fn inversion<I: Add<I> + for<'a> AddAssign<&'a I> + Sum<I> + Product<I>>(
14        &self,
15    ) -> I {
16        let n = self.len();
17        let ord = {
18            let mut ord: Vec<_> = (0..n).collect();
19            ord.sort_unstable_by(|&il, &ir| {
20                self[il].cmp(&self[ir]).then_with(|| il.cmp(&ir))
21            });
22            ord
23        };
24
25        let zero = || None.into_iter().sum::<I>();
26        let one = || None.into_iter().product::<I>();
27        let mut res = zero();
28        let mut sum: Vec<_> = (0..=n).map(|_| zero()).collect();
29        for i in ord.iter().map(|&i| i + 1) {
30            {
31                let mut i = i;
32                while i <= n {
33                    res += &sum[i];
34                    i += i & i.wrapping_neg();
35                }
36            }
37            {
38                let mut i = i;
39                while i > 0 {
40                    sum[i] += &one();
41                    i -= i & i.wrapping_neg();
42                }
43            }
44        }
45
46        res
47    }
48}
49
50#[test]
51fn sanity_check() {
52    assert_eq!([1, 5, 4, 2, 3].inversion::<usize>(), 5);
53    assert_eq!([1, 2, 3, 4, 5].inversion::<usize>(), 0);
54    assert_eq!([5, 4, 3, 2, 1].inversion::<usize>(), 10);
55    assert_eq!([1, 1, 1, 1, 1].inversion::<usize>(), 0);
56
57    let empty: [(); 0] = [];
58    assert_eq!(empty.inversion::<usize>(), 0);
59}
inversion/lib.rs

inversion/
lib.rs
