63 lines
1.6 KiB
Rust
63 lines
1.6 KiB
Rust
use std::io::{read_to_string, stdin};
|
|
|
|
fn invcnt(arr: &mut Vec<usize>, lo: usize, hi: usize) -> usize {
|
|
let delta = hi - lo;
|
|
if delta == 0 {
|
|
return 0;
|
|
} else if delta == 1 {
|
|
return 0;
|
|
} else if delta == 2 {
|
|
if arr[lo] > arr[lo + 1] {
|
|
let temp = arr[lo + 1];
|
|
arr[lo + 1] = arr[lo];
|
|
arr[lo] = temp;
|
|
return 1;
|
|
} else {
|
|
return 0;
|
|
}
|
|
} else {
|
|
let mut res = 0;
|
|
let mut left = lo;
|
|
let mut right = (lo + hi) / 2;
|
|
let left_end = right;
|
|
let right_end = hi;
|
|
let mut v = vec![];
|
|
res += invcnt(arr, left, left_end);
|
|
res += invcnt(arr, right, right_end);
|
|
while left < left_end && right < right_end {
|
|
if arr[left] > arr[right] {
|
|
v.push(arr[right]);
|
|
res += left_end - left;
|
|
right += 1;
|
|
} else {
|
|
v.push(arr[left]);
|
|
left += 1;
|
|
}
|
|
}
|
|
while left < left_end {
|
|
v.push(arr[left]);
|
|
left += 1;
|
|
}
|
|
while right < right_end {
|
|
v.push(arr[right]);
|
|
right += 1;
|
|
}
|
|
for (i, &e) in v.iter().enumerate() {
|
|
arr[lo + i] = e;
|
|
}
|
|
return res;
|
|
}
|
|
}
|
|
|
|
fn main() {
|
|
let temp = read_to_string(stdin()).unwrap();
|
|
let mut iter = temp
|
|
.split_ascii_whitespace()
|
|
.map(|x| x.parse::<usize>().unwrap());
|
|
let n = iter.next().unwrap();
|
|
let mut arr = (0..n).map(|_| iter.next().unwrap()).collect::<Vec<_>>();
|
|
|
|
let res = invcnt(&mut arr, 0, n);
|
|
println!("{}", res);
|
|
}
|