2022-12-20：二狗买了一些小兵玩具，和大胖一起玩， 一共有 n 个小兵，这 n 个小兵拍成一列， 第 i 个小兵战斗力为 hi，然后他们两个开始对小兵进行排列， 一共进行 m 次操作，二狗每次操作选择一个数 k，

use rand::Rng;use std::cmp::Ordering;use std::collections::BTreeSet;use std::iter::repeat;fn main() {    let mut arr = vec![3, 2, 6, 7, 5, 1];    let mut op = vec![vec![3, 0], vec![4, 1], vec![2, 0]];    let ans2 = game2(&mut arr, &mut op);    println!("ans2 = {:?}", ans2);    let nn: i32 = 200;    let mm: i32 = 100;    let vv: i32 = 200;    let test_time: i32 = 5000;    println!("测试开始");    for i in 0..test_time {        let n: i32 = rand::thread_rng().gen_range(0, nn) + 1;        let m: i32 = rand::thread_rng().gen_range(0, mm) + 1;        let mut arr = random_array(n, vv);        let mut op = random_op(m, n);        let ans1 = game1(&mut arr, &mut op);        let ans2 = game2(&mut arr, &mut op);        if ans1 != ans2 {            println!("出错了!");            println!("i = {}", i);            println!("ans1 = {:?}", ans1);            println!("ans2 = {:?}", ans2);            break;        }    }    println!("测试结束");}
// 暴力方法// 为了验证fn game1(arr: &mut Vec<i32>, op: &mut Vec<Vec<i32>>) -> Vec<i32> {    let n = arr.len() as i32;    let mut help: Vec<i32> = repeat(0).take(n as usize).collect();    for i in 0..n {        help[i as usize] = arr[i as usize];    }    for o in op.iter() {        if o[1] == 0 {            help[0..o[0] as usize].sort_by(|a, b| a.cmp(b));        } else {            help[0..o[0] as usize].sort_by(|a, b| b.cmp(a));        }    }    let mut ans: Vec<i32> = repeat(0).take(n as usize).collect();    for i in 0..n {        ans[i as usize] = help[i as usize];    }    return ans;}
// 正式方法// 时间复杂度O(M) + O(N*logN)fn game2(arr: &mut Vec<i32>, op: &mut Vec<Vec<i32>>) -> Vec<i32> {    let n = arr.len() as i32;    let m = op.len() as i32;    let mut stack: Vec<i32> = repeat(0).take(m as usize).collect();    let mut r = 0;    for i in 0..m {        while r != 0 && op[stack[(r - 1) as usize] as usize][0] <= op[i as usize][0] {            r -= 1;        }        stack[r as usize] = i;        r += 1;    }    let mut ans: Vec<i32> = repeat(0).take(n as usize).collect();    let mut ansi = n - 1;    let mut l = 0;    while ansi >= op[stack[l as usize] as usize][0] {        ans[ansi as usize] = arr[ansi as usize];        ansi -= 1;    }    let mut sorted: BTreeSet<Number> = BTreeSet::new();    for i in 0..op[stack[l as usize] as usize][0] {        sorted.insert(Number::new(arr[i as usize], i));    }    while l != r {        // 当前处理的指令        let cur = &op[stack[l as usize] as usize];        l += 1;        if l != r {            let mut next = &op[stack[l as usize] as usize];            let num = cur[0] - next[0];            if cur[1] == 0 {                for i in 0..num {                    ans[ansi as usize] = sorted.pop_last().unwrap().value;                    ansi -= 1;                }            } else {                for i in 0..num {                    ans[ansi as usize] = sorted.pop_first().unwrap().value;                    ansi -= 1;                }            }        } else {            if cur[1] == 0 {                while sorted.len() > 0 {                    ans[ansi as usize] = sorted.pop_last().unwrap().value;                    ansi -= 1;                }            } else {                while sorted.len() > 0 {                    ans[ansi as usize] = sorted.pop_first().unwrap().value;                    ansi -= 1;                }            }        }    }    return ans;}
struct Number {    value: i32,    index: i32,}
impl Number {    fn new(v: i32, i: i32) -> Self {        Self { value: v, index: i }    }}
impl Ord for Number {    fn cmp(&self, other: &Self) -> Ordering {        if self.value != other.value {            self.value.cmp(&other.value)        } else {            self.index.cmp(&other.index)        }    }}
impl PartialOrd for Number {    fn partial_cmp(&self, other: &Self) -> Option<Ordering> {        Some(self.cmp(other))    }}
impl PartialEq for Number {    fn eq(&self, other: &Self) -> bool {        (self.value, &self.index) == (other.value, &other.index)    }}
impl Eq for Number {}
// 为了测试fn random_array(n: i32, v: i32) -> Vec<i32> {    let mut ans: Vec<i32> = repeat(0).take(n as usize).collect();    for i in 0..n {        ans[i as usize] = rand::thread_rng().gen_range(0, v) + 1;    }    return ans;}
// 为了测试fn random_op(m: i32, n: i32) -> Vec<Vec<i32>> {    let mut ans: Vec<Vec<i32>> = repeat(repeat(0).take(2).collect())        .take(m as usize)        .collect();    for i in 0..m {        ans[i as usize][0] = rand::thread_rng().gen_range(0, n + 1);        ans[i as usize][1] = rand::thread_rng().gen_range(0, 2);    }    return ans;}
// 为了测试fn is_equal(arr1: &mut Vec<i32>, arr2: &mut Vec<i32>) -> bool {    if arr1.len() != arr2.len() {        return false;    }    for i in 0..arr1.len() {        if arr1[i as usize] != arr2[i as usize] {            return false;        }    }    return true;}