2022-12-12：有 n 个城市，城市从 0 到 n-1 进行编号。小美最初住在 k 号城市中 在接下来的 m 天里，小美每天会收到一个任务 她可以选择完成当天的任务或者放弃该任务 第 i 天的任务需要在 ci 号城市完成，

use rand::Rng;use std::iter::repeat;fn main() {    let nn: i32 = 100;    let mm: i32 = 100;    let vv: i32 = 10000;    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 k: i32 = rand::thread_rng().gen_range(0, n);        let mut c = random_array(m, n);        let mut a = random_array(m, vv);        let mut b = random_array(m, vv);        let ans1 = max_porfit1(n, m, k, &mut c, &mut a, &mut b);        let ans2 = max_porfit2(n, m, k, &mut c, &mut a, &mut b);        if ans1 != ans2 {            println!("出错了!");            println!("i = {}", i);            println!("ans1 = {}", ans1);            println!("ans2 = {}", ans2);            break;        }    }    println!("测试结束");}
// 暴力方法// 时间复杂度O(N^2)// 为了验证fn max_porfit1(    n: i32,    m: i32,    k: i32,    c: &mut Vec<i32>,    a: &mut Vec<i32>,    b: &mut Vec<i32>,) -> i32 {    let mut dp: Vec<Vec<i32>> = repeat(repeat(-1).take(m as usize).collect())        .take(n as usize)        .collect();    return process1(k, 0, m, c, a, b, &mut dp);}
// cur : 小美当前在哪！// i : 当前面临的是任务编号！// m : 一共有多少任务，固定// c[i] : 第i号任务要在哪个城里完成// a[i] : 恰好在！收益// b[i] : 赶过去！收益// 返回 : i....... 小美获得的最大收益fn process1(    cur: i32,    i: i32,    m: i32,    c: &mut Vec<i32>,    a: &mut Vec<i32>,    b: &mut Vec<i32>,    dp: &mut Vec<Vec<i32>>,) -> i32 {    if i == m {        return 0;    }    if dp[cur as usize][i as usize] != -1 {        return dp[cur as usize][i as usize];    }    // 可能性1 : 不做任务，彻底放弃，留在原地    let p1 = process1(cur, i + 1, m, c, a, b, dp);    // 可能性2 : 做任务，要看看cur在哪，来获得收益    let mut p2 = 0;    if cur == c[i as usize] {        p2 = a[i as usize] + process1(c[i as usize], i + 1, m, c, a, b, dp);    } else {        p2 = b[i as usize] + process1(c[i as usize], i + 1, m, c, a, b, dp);    }    let ans = get_max(p1, p2);    dp[cur as usize][i as usize] = ans;    return ans;}
fn get_max<T: Clone + Copy + std::cmp::PartialOrd>(a: T, b: T) -> T {    if a > b {        a    } else {        b    }}
// 正式方法// 时间复杂度O(N*logN)fn max_porfit2(    n: i32,    m: i32,    k: i32,    c: &mut Vec<i32>,    a: &mut Vec<i32>,    b: &mut Vec<i32>,) -> i32 {    let mut st = SegmentTree::new(n);    st.update(k, 0);    let mut ans = 0;    for i in 0..m {        // c[i]        let cur_ans = get_max(            get_max(                st.max(0, c[i as usize] - 1),                st.max(c[i as usize] + 1, n - 1),            ) + b[i as usize],            st.max(c[i as usize], c[i as usize]) + a[i as usize],        );        ans = get_max(ans, cur_ans);        st.update(c[i as usize], cur_ans);    }    return ans;}
struct SegmentTree {    n: i32,    max: Vec<i32>,}impl SegmentTree {    fn new(nn: i32) -> Self {        let n = nn;        let max: Vec<i32> = repeat(i32::MIN).take(((n + 1) << 2) as usize).collect();        Self { n, max }    }
    fn max(&mut self, mut l: i32, mut r: i32) -> i32 {        l += 1;        r += 1;        if l > r {            return i32::MIN;        }        return self.max0(l, r, 1, self.n, 1);    }
    fn update(&mut self, mut i: i32, v: i32) {        i += 1;        self.update0(i, i, v, 1, self.n, 1);    }
    fn push_up(&mut self, rt: i32) {        self.max[rt as usize] = get_max(            self.max[(rt << 1) as usize],            self.max[(rt << 1 | 1) as usize],        );    }
    fn update0(&mut self, ll: i32, rr: i32, cc: i32, l: i32, r: i32, rt: i32) {        if ll <= l && r <= rr {            self.max[rt as usize] = get_max(self.max[rt as usize], cc);            return;        }        let mid = (l + r) >> 1;        if ll <= mid {            self.update0(ll, rr, cc, l, mid, rt << 1);        }        if rr > mid {            self.update0(ll, rr, cc, mid + 1, r, rt << 1 | 1);        }        self.push_up(rt);    }
    fn max0(&mut self, ll: i32, rr: i32, l: i32, r: i32, rt: i32) -> i32 {        if ll <= l && r <= rr {            return self.max[rt as usize];        }        let mid = (l + r) >> 1;        let mut left = i32::MIN;        let mut right = i32::MIN;        if ll <= mid {            left = self.max0(ll, rr, l, mid, rt << 1);        }        if rr > mid {            right = self.max0(ll, rr, mid + 1, r, rt << 1 | 1);        }        return get_max(left, right);    }}
// 为了测试fn random_array(n: i32, v: i32) -> Vec<i32> {    let mut ans = vec![];    for i in 0..n {        ans.push(rand::thread_rng().gen_range(0, v));    }    ans}