competitive_library/algorithm/
inversion_number.rs

1//! 転倒数
2pub fn inversion_number<T: Copy + PartialOrd>(array: &[T]) -> i64 {
3    count_merge(&mut array.to_vec(), 0..array.len())
4}
5fn count_merge<T: Copy + PartialOrd>(array: &mut Vec<T>, range: std::ops::Range<usize>) -> i64 {
6    let length = range.len() as i64;
7    if length <= 1 {
8        return 0;
9    }
10
11    let mut count = 0;
12    let mid = (range.start + range.end) / 2;
13    count += count_merge(array, range.start..mid);
14    count += count_merge(array, mid..range.end);
15
16    let b = array
17        .iter()
18        .skip(range.start)
19        .take(mid - range.start)
20        .copied()
21        .collect::<Vec<_>>();
22    let c = array
23        .iter()
24        .skip(mid)
25        .take(range.end - mid)
26        .copied()
27        .collect::<Vec<_>>();
28
29    let (mut ai, mut bi, mut ci) = (0, 0, 0);
30
31    while ai < length {
32        if bi < b.len() && (ci == c.len() || b[bi] <= c[ci]) {
33            array[range.start + ai as usize] = b[bi];
34            ai += 1;
35            bi += 1;
36        } else {
37            count += length / 2 - bi as i64;
38            array[range.start + ai as usize] = c[ci];
39            ai += 1;
40            ci += 1;
41        }
42    }
43    count
44}
45
46#[cfg(test)]
47mod tests {
48    use super::*;
49    #[test]
50    fn test_inversion_number() {
51        let array = {
52            let v = vec![
53                (vec![3, 1, 5, 4, 2], 5),
54                (vec![3, 5, 2, 1, 4], 6),
55                (vec![3, 1, 2], 2),
56                (vec![6, 1, 5, 8, 2, 3, 4, 7], 12),
57                (vec![7, 6, 1, 5, 8, 2, 3, 10, 4, 9], 19),
58                (
59                    vec![
60                        63, 16, 24, 7, 29, 57, 65, 26, 36, 32, 50, 5, 34, 1, 18, 15, 49, 9, 47, 53,
61                        10, 35, 76, 79,
62                    ],
63                    122,
64                ),
65                (
66                    vec![
67                        0, 18, 35, 2, 31, 33, 32, 6, 11, 15, 36, 19, 42, 23, 9, 20, 24, 3, 10, 47,
68                        8, 38, 5, 37, 46,
69                    ],
70                    125,
71                ),
72            ];
73            v
74        };
75
76        for (input, ans) in array {
77            assert_eq!(inversion_number(&input), ans);
78        }
79    }
80}
competitive_library/algorithm/inversion_number.rs

competitive_library/algorithm/
inversion_number.rs
