2023-02-16：两种颜色的球，蓝色和红色，都按 1～n 编号，共计 2n 个， 为方便放在一个数组中，红球编号取负，篮球不变，并打乱顺序， 要求同一种颜色的球按编号升序排列，可以进行如下操作： 交换相邻

use std::collections::HashMap;use std::iter::repeat;fn main() {    let mut arr = vec![3, -3, 1, -4, 2, -2, -1, 4];    println!("{}", min_swaps(&mut arr));}
// [3,-3,1,-4,2,-2,-1,4]//    -3   -4   -2 -1   -> -1 -2 -3 -4//  3    1    2       4 ->  1  2  3  4
// 这个题写对数器太麻烦了// 所以这就是正式解fn min_swaps(arr: &mut Vec<i32>) -> i32 {    let n = arr.len() as i32;    let mut map: HashMap<i32, i32> = HashMap::new();    let mut top_a = 0;    let mut top_b = 0;    for i in 0..n {        if arr[i as usize] > 0 {            top_a = get_max(top_a, arr[i as usize]);        } else {            top_b = get_max(top_b, abs(arr[i as usize]));        }        map.insert(arr[i as usize], i);    }    let mut it = IndexTree::new(n);    for i in 0..n {        it.add(i, 1);    }    return f(top_a, top_b, &mut it, n - 1, &mut map);}
// 可以改二维动态规划！// 因为it的状态，只由topA和topB决定// 所以it的状态不用作为可变参数！fn f(top_a: i32, top_b: i32, it: &mut IndexTree, end: i32, map: &mut HashMap<i32, i32>) -> i32 {    if top_a == 0 && top_b == 0 {        return 0;    }    let mut p1 = i32::MAX;    let mut p2 = i32::MAX;    let mut index: i32;    let mut cost: i32;    let mut next: i32;    if top_a != 0 {        index = *map.get(&top_a).unwrap();        cost = it.sum(index, end) - 1;        it.add(index, -1);        next = f(top_a - 1, top_b, it, end, map);        it.add(index, 1);        p1 = cost + next;    }    if top_b != 0 {        index = *map.get(&(-top_b)).unwrap();        cost = it.sum(index, end) - 1;        it.add(index, -1);        next = f(top_a, top_b - 1, it, end, map);        it.add(index, 1);        p2 = cost + next;    }    return get_min(p1, p2);}fn get_max<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {    if a > b {        a    } else {        b    }}
fn get_min<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {    if a < b {        a    } else {        b    }}
fn abs(a: i32) -> i32 {    if a < 0 {        -a    } else {        a    }}struct IndexTree {    tree: Vec<i32>,    nn: i32,}impl IndexTree {    pub fn new(size: i32) -> Self {        Self {            tree: repeat(0).take((size + 1) as usize).collect(),            nn: size,        }    }
    pub fn add(&mut self, mut i: i32, v: i32) {        i += 1;        while i <= self.nn {            self.tree[i as usize] += v;            i += i & -i;        }    }
    pub fn sum(&mut self, l: i32, r: i32) -> i32 {        return if l == 0 {            self.sum0(r + 1)        } else {            self.sum0(r + 1) - self.sum0(l)        };    }
    fn sum0(&mut self, mut index: i32) -> i32 {        let mut ans = 0;        while index > 0 {            ans += self.tree[index as usize];            index -= index & -index;        }        return ans;    }}