nekolib/algo/
inversion.rs

1pub trait Inversion {
2    fn inversion(&self) -> u64;
3}
4
5impl<T: Ord> Inversion for [T] {
6    fn inversion(&self) -> u64 {
7        let n = self.len();
8        let ord = {
9            let mut ord: Vec<_> = (0..n).collect();
10            ord.sort_unstable_by(|&il, &ir| {
11                self[il].cmp(&self[ir]).then_with(|| il.cmp(&ir))
12            });
13            ord
14        };
15
16        let mut res = 0;
17        let mut sum = vec![0; n + 1];
18        for i in ord.iter().map(|&i| i + 1) {
19            {
20                let mut i = i;
21                while i <= n {
22                    res += sum[i];
23                    i += i & i.wrapping_neg();
24                }
25            }
26            {
27                let mut i = i;
28                while i > 0 {
29                    sum[i] += 1;
30                    i -= i & i.wrapping_neg();
31                }
32            }
33        }
34
35        res
36    }
37}
38
39#[test]
40fn sanity_check() {
41    assert_eq!([1, 5, 4, 2, 3].inversion(), 5);
42    assert_eq!([1, 2, 3, 4, 5].inversion(), 0);
43    assert_eq!([5, 4, 3, 2, 1].inversion(), 10);
44    assert_eq!([1, 1, 1, 1, 1].inversion(), 0);
45
46    let empty: [(); 0] = [];
47    assert_eq!(empty.inversion(), 0);
48}
nekolib/algo/inversion.rs

nekolib/algo/
inversion.rs
