haar_lib/algo/
inversion_number.rs

1//! 転倒数
2
3/// 数列の転倒数を計算する。
4///
5/// **Time complexity** $O(n \log n)$
6pub fn inversion_number<T: PartialOrd + Copy>(a: &mut [T]) -> u64 {
7    let n = a.len();
8
9    if n <= 1 {
10        return 0;
11    }
12
13    let mut ret = 0;
14
15    let b = &mut a[0..n / 2].to_vec();
16    let c = &mut a[n / 2..n].to_vec();
17
18    ret += inversion_number(b);
19    ret += inversion_number(c);
20
21    let mut bi = 0;
22    let mut ci = 0;
23
24    for ai in a.iter_mut() {
25        if bi < b.len() && (ci == c.len() || b[bi] <= c[ci]) {
26            *ai = b[bi];
27            bi += 1;
28        } else {
29            ret += (n / 2 - bi) as u64;
30            *ai = c[ci];
31            ci += 1;
32        }
33    }
34
35    ret
36}
37
38#[cfg(test)]
39mod tests {
40    use super::*;
41
42    #[test]
43    fn test() {
44        assert_eq!(inversion_number(&mut [3, 5, 2, 1, 4]), 6);
45        assert_eq!(inversion_number(&mut [3, 1, 2]), 2);
46    }
47}
haar_lib/algo/inversion_number.rs

haar_lib/algo/
inversion_number.rs
